Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
| reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 08:41] – root1 | reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 14:50] (current) – root1 | ||
|---|---|---|---|
| Line 10: | Line 10: | ||
| ===== 2.4 Actually Generating Sentences from a Grammar ===== | ===== 2.4 Actually Generating Sentences from a Grammar ===== | ||
| - | generate $a^nb^nc^n$ grammar from | + | generate $a^nb^nc^n$ grammar from using |
| + | |||
| + | < | ||
| + | 1. Ss -> abc | aSQ | ||
| + | 2. bQc -> bbcc | ||
| + | 3. cQ -> Qc | ||
| + | </ | ||
| + | |||
| + | This way of doing things is called // | ||
| + | |||
| + | ==== The CF Case ==== | ||
| + | |||
| + | < | ||
| + | S = N | L, '&', | ||
| + | N = ' | ||
| + | L = N, ',', | ||
| + | |||
| + | </ | ||
| + | |||
| + | ===== 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 ==== | ||
| + | |||
| + | < | ||
| + | // A demo grammar for grammar cleaning | ||
| + | S ---> AB|DE | ||
| + | A ---> a | ||
| + | B ---> bC | ||
| + | C ---> c | ||
| + | D ---> dF | ||
| + | E ---> e | ||
| + | F ---> fD | ||
| + | </ | ||
| + | |||
| + | === 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 ====== | ||
| + | |||
| + | |||
| + | |||
root1