Parser generator (bootstrap)

[andrew-johnson-4]

Bring this story to life:

rhs        := [a-z][_a-zA-Z0-9]*   //Variable
            | ( rhs* )             //Function Application
            | λ rhs* . rhs*        //Lambda Function
            | [^ ]+                //Literal Value

binding    := [a-zA-Z0-9]+ [:] [=] rhs \n

program    := binding*

example recursive descent parser:

• top to bottom (previous rule candidates have higher precedence over following rule candidates)
• terminal to non-terminal (terminal symbols have higher precedence over non-terminal symbols within same rule)
• left to right (left symbols have higher precedence over right symbols within same rule)
• this parser generator is for up-to free grammars and requires infinite lookahead in worst case

nibble-lhs := λ"a" a. a
nibble-rhs := λa "a". a
nibble-nonterminal := λ(nibble-lhs a) b. a b
nibble-empty := λ. "a"
nibble-tokens := λ(ident n) (eq _) (rhs r). (Assign n r)

[andrew-johnson-4]

Initial parser compiler will be implemented in Rust. These rule forms may be relaxed later to accomplish more natural implementation of higher-order grammars. However, for now the emphasis is on simple efficient implementation of context-free grammars.

#rule-name-x binding-y := (Regex pattern)
#rule-name-x binding-y := (Scan left-rule middle-rule right-rule)
#rule-name-x binding-y := (Sequence rules...)
#rule-name-x binding-y := (Descend rule-name-z)