reading_notes:parsing_techniques_a_practical_guide_second_edition

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 08:11] – root1reading_notes:parsing_techniques_a_practical_guide_second_edition [2024/06/18 14:50] (current) – root1
Line 7: Line 7:
 | 3            | FS           | production list                 | | 3            | FS           | production list                 |
 | 4            | FC           | production element              | | 4            | FC           | production element              |
 +
 +===== 2.4 Actually Generating Sentences from a Grammar =====
 +
 +generate $a^nb^nc^n$ grammar from using
 +
 +<codeprism>
 +1. Ss -> abc | aSQ 
 +2. bQc -> bbcc
 +3. cQ -> Qc
 +</codeprism>
 +
 +This way of doing things is called //breadth-first production//; computers are better at it than people.
 +
 +==== The CF Case ====
 +
 +<codeprism lang=ebnf>
 +S = N | L, '&', N ;
 +N = 't' | 'd' | 'h' ;
 +L = N, ',', L | N ;
 +
 +</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 ======
 +
 +
 +
 +
 +
  • reading_notes/parsing_techniques_a_practical_guide_second_edition.1718698316.txt.gz
  • Last modified: 2024/06/18 08:11
  • by root1