Difference between revisions of "Notes:Parsing"

Latest revision as of 19:06, 24 September 2016

Algorithms

These algorithms apply to CFGs:

• [ilmath]\alpha,\beta,\gamma,\ldots[/ilmath] denote sequences (possibly empty) of terminals and nonTerminals Caution:Done from memory, still to do, check this
  • EXCEPT: [ilmath]\varepsilon[/ilmath] - which means "the empty string"
• [ilmath]\text{a},\text{b},\text{c} [/ilmath] terminal symbols Caution:Check
• [ilmath]a,b,c[/ilmath] terminal or non terminal symbols Caution:Check

[ilmath]\text{Nullable}[/ilmath]

Definition of [ilmath]\nullable{\alpha} [/ilmath] (a predicate):

• [ilmath]\nullable{\alpha}\iff[\alpha\dot\implies\varepsilon][/ilmath]

The algorithm for [ilmath]\text{Nullable} [/ilmath] is defined by structural induction:

1. [ilmath]\nullable{\varepsilon}=\text{true}[/ilmath]
2. [ilmath]\nullable{a\text{a} }=\text{false}[/ilmath]
3. [ilmath]\nullable{\alpha\beta}=\nullable{\alpha}\wedge\nullable{\beta}[/ilmath]
4. [ilmath]\nullable{N}=\nullable{\alpha_1}\vee\cdots\vee\nullable{\alpha_n}[/ilmath]
   • Where [ilmath]N[/ilmath] consists of [ilmath]n[/ilmath] productions, [ilmath]N\rightarrow \alpha_1[/ilmath] to [ilmath]N\rightarrow\alpha_n[/ilmath]

[ilmath]\text{First} [/ilmath]

Definition of [ilmath]\text{First}(\alpha)[/ilmath] (a set):

• [ilmath]c\in\first{\alpha}\iff\exists\beta\ \text{(possibly empty)}[\alpha\dot\implies c\beta][/ilmath]

The algorithm for [ilmath]\text{First} [/ilmath] is also defined by structural induction:

1. [ilmath]\first{\varepsilon}[/ilmath] [ilmath]=[/ilmath] [ilmath]\emptyset[/ilmath]
2. [ilmath]\first{\text{a} }=\{\text{a}\}[/ilmath]
3. [ilmath]\first{\alpha\beta}=\left\{\begin{array}{lr}\first{\alpha}\cup\first{\beta}&\text{if }\nullable{\alpha}\\ \first{\alpha} & \text{if not }\nullable{\alpha} \end{array}\right.[/ilmath]
4. [ilmath]\first{N}=\first{\alpha_1}\cup\cdots\cup\first{\alpha_n}[/ilmath]
   • Where [ilmath]N[/ilmath] has [ilmath]n[/ilmath] productions, [ilmath]N\rightarrow\alpha_1[/ilmath] to [ilmath]N\rightarrow\alpha_n[/ilmath]

[ilmath]\text{Follow} [/ilmath]

Definition of [ilmath]\follow{N} [/ilmath] (a set (of terminals)):

• [ilmath]\text{a}\in\follow{\alpha}\iff\exists[/ilmath] (a derivation from the start symbol, [ilmath]S[/ilmath], such that [ilmath]S\dot\implies\alpha N\text{a}\beta[/ilmath] for [ilmath]\alpha,\beta[/ilmath] (possibly empty) sequences of grammar symbols)

Note that unlike the others given this is not a property directly from the argument, but a property based on all productions that use [ilmath]N[/ilmath] (directly or not)

Algorithm to come.