Differences

This shows you the differences between two versions of the page.

--- reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 09:35] – [2.4 Actually Generating Sentences from a Grammar] root1
+++ reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 14:50] (current) – root1
@@ Line 28: / Line 28: @@
 </codeprism>
+===== The Limitations of CF and FS Grammars =====
+==== The uvwxy Theorem(pumping lemma) ====
+===== 2.9 Hygiene in Context-Free Grammars =====
+Problems
+  - Undefined Non-Terminals
+  - Unreachable Non-Terminals
+  - Non-Productive Rules and Non-Terminals
+    - Suppose X has as its only rule X → aX and suppose X can be reached from the start symbol. Now X will still not contribute anything to the sentences of the language of the grammar, since once X is introduced, there is no way to get rid of it: X is a non-productive non-terminal.
+  - loops
+These four groups together are called //useless non-terminals//.
+==== 2.9.5 Cleaning up a Context-Free Grammar ====
+<codeprism>
+// A demo grammar for grammar cleaning
+S ---> AB|DE
+A ---> a
+B ---> bC
+C ---> c
+D ---> dF
+E ---> e
+F ---> fD
+</codeprism>
+=== 2.9.5.1 Removing Non-Productive Rules ===
+We solve this dilemma by first marking all rules and non-terminals as “Don’t
+know”. We now go through the grammar of **demo** and for each rule for which
+we do know that all its right-hand side members are productive, we mark the rule
+and the non-terminal it defines as “Productive”.
+=== 2.9.5.2 Removing Unreachable Non-Terminals ===
+===== 2.10 Set Properties of Context-Free and Regular Languages =====
+====== 3 Introduction to Parsing ======