# IT:AD:TinyPG #



<callout type="Navigation" class="small">

* [[../|(UP)]]
{{indexmenu>.#2|nsort tsort}}


</callout>


<panel title="Summary">

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


</panel>


## Terminology ##

* BNF (Backus-Naur Form)
    * [Ref:Wikipedia](http://en.wikipedia.org/wiki/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.



### Filtering

* [http://stackoverflow.com/questions/11947225/filter-command-design-approach](http://stackoverflow.com/questions/11947225/filter-command-design-approach)

## Resources ##

* [http://www.codeproject.com/Articles/28294/a-Tiny-Parser-Generator-v1-2](http://www.codeproject.com/Articles/28294/a-Tiny-Parser-Generator-v1-2)
* [https://github.com/SickheadGames/TinyPG](https://github.com/SickheadGames/TinyPG)
* [http://www.codeproject.com/Articles/241830/a-Tiny-Expression-Evaluator](http://www.codeproject.com/Articles/241830/a-Tiny-Expression-Evaluator)
* [http://en.wikipedia.org/wiki/Terminal_symbol](http://en.wikipedia.org/wiki/Terminal_symbol)
* [http://en.wikipedia.org/wiki/LL%281%29](http://en.wikipedia.org/wiki/LL%281%29)