reading_notes:parsing_techniques_a_practical_guide_second_edition [Lingao's Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 2 Grammars as a Generating Device ======
==== 2.3.5 Conclusion ====

^ Chomsky type ^ Grammar type ^ Most complicated data structure ^
| 0 / 1        | PS / CS      | production dag                  |
| 2            | CF           | production tree                 |
| 3            | FS           | production list                 |
| 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 ======