Get the latest tech news

Parsing and all that

A web log. Mostly about computer science-y stuff.

Simple automata for each grammar rule from the last exampledigraph "Simple automata for each grammar rule from the last example" { bgcolor="transparent"; node [shape=circle, fixedsize=shape, width=0.5, fontcolor="#010101", color="#010101"]; edge [fontcolor="#010101", color="#010101"]; rankdir=LR; subgraph { start1 [shape=none, label="", width=0]; S₁ [shape=doublecircle, width=0.4]; start1 -> S₁₀; S₁₀ -> S₁₁ [label="A"]; S₁₁ -> S₁₂ [label="a"]; S₁₂ -> S₁₃ [label="b"]; S₁₃ -> S₁₄ [label="A"]; S₁₄ -> S₁₅ [label="b"]; S₁₅ -> S₁ [label="a"]; } subgraph { node [style=filled, fillcolor="#ddd"]; start2 [style="", shape=none, label="", width=0]; A₂ [shape=doublecircle, width=0.4]; start2 -> A₂₀; A₂₀ -> A₂ [label="a"]; } subgraph { node [style=filled, fillcolor="#aaa"]; start3 [style="", shape=none, label="", width=0]; A₃ [shape=doublecircle, width=0.4]; start3 -> A₃; } }Simple automata for each grammar rule from the last examplestart1S₁₀S₁₀start1->S₁₀S₁S₁S₁₁S₁₁S₁₀->S₁₁AS₁₂S₁₂S₁₁->S₁₂aS₁₃S₁₃S₁₂->S₁₃bS₁₄S₁₄S₁₃->S₁₄AS₁₅S₁₅S₁₄->S₁₅bS₁₅->S₁astart2A₂₀A₂₀start2->A₂₀A₂A₂A₂₀->A₂astart3A₃A₃start3->A₃ Since you’re writing plain old code with function calls, you can imagine people have found nice ways to extend and adapt the pattern of recursive descent parsers. That’s keeps our process simple, our automaton small, but it also causes us to lose exactly the information we need to resolve the reduce-reduce conflict in box 3 above: the left context.

Get the Android app