IT:AD:TinyPG

Summary

TinyPG is a compact LL(1) which produces no dependencies beyond a tiny set of sources (parser,scanner,parsetree).

Terminology

  • BNF (Backus-Naur Form)

    Example:

    <symbol> ::= expression <fullname> ::= <firstname> <middlename> <lastname>

Grammars are defined by production rules specifying which symbols can be replaced by other symbols. Symbols can be of one of two types: terminal symbols are symbols that cannot be replaced with something else, non-terminal symbols are symbols that can be be replaced with something else.

Eg:

<integer> ::= ['-'] <digit> {<digit>}
<digit> ::= '0' |'1' |'2' |'3' |'4' |'5' |'6' |'7' |'8' |'9' 
  • {-,0,1,2,3,4,5,6,7,8,9} are terminal symbols.
  • <digit> and <integer> are non-terminal.

Parsing

An LL Parser is a Top-Down Parser that parses from left to right, constructing a Leftmost derivation of the sentence.

An LL(1) parser is one that uses 1 lookahead token when parsing, that does not need to backtrack.

Filtering

Resources