diff options
slides for the parser generators
1 files changed, 100 insertions, 0 deletions
| -rw-r--r-- | website/content/slides/04_parser_generators/_index.md | 100 |
diff --git a/website/content/slides/04_parser_generators/_index.md b/website/content/slides/04_parser_generators/_index.md new file mode 100644 index 0000000..5bca173 --- /dev/null +++ b/website/content/slides/04_parser_generators/_index.md @@ -0,0 +1,100 @@ +--- +title: "Parser Generators" +date: 2018-10-02T17:45:53+03:00 +draft: false +outputs: ["Reveal"] +--- + +# Parser Generators + +Contents: + +- LR Parsers +- Bison + +--- +# LR Parsers + +- L - the parsers reads the text only once, without backing up +- R - rightmost derivation +- bottom-up parser +- LR(1) - 1 - the number of look-ahead symbols necessary to parse the grammar + +--- +### Rightmost derivation + +- The tree created for an expression would replace the rightmost non-terminal at + each step + +--- +### Bottom-up + +The tree is constructed from the bottom - from the leaves to the root. + +--- +## Algorithm + +The parser: + +- keeps a stack of the parsed sub-trees so far +- runs in a loop over the input and on each iteration it does either +a *shift* or a *reduce* action. + + - shift - push the token on the stack + - reduce - pop N subtrees from the stack, make a new tree that has them as + children and push it to the stack + +--- +#### Ring any bells? + +--- +#### Ring any bells? + +Same as the shunting yard algorithm, but: +- without the operator precedence + - it replaced by the grammar structure +- There all the rules had just two children + +--- +### To shift or to reduce? + +- Depends on the grammar rules. +- The algorithm uses a Finite State Automaton (FSA) + +--- +### To shift or to reduce? + +The FSA has for each (state, next token) -> (action, next state) + +- action - whether to shift or reduce + +--- +# Bison + +- Bison generates LR(1) and GLR parsers + - GLR parsers can have arbitrary lookahead and be ambigous +- You don't always have to convert the grammar in an LR form + - operator precedence and assiociativity are handled for your + +--- +### Input + + %{ + /* verbatim copy */ + %} + + /* definitions */ + + %% + /* rules */ + %% + /* verbatim copy */ + +--- +### Parsing expressions + +https://github.com/SofiaCPP/IPL/blob/master/demo/bison/calc/parser.y + +--- +# ? + |
