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)
- A notation fo context-free grammars.
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.