From 63f10cd40a27b109863895381a283b8229c5664f Mon Sep 17 00:00:00 2001 From: Dimitar Trendafilov Date: Wed, 24 Oct 2018 20:43:33 +0300 Subject: slides for the parser generators --- .../content/slides/04_parser_generators/_index.md | 100 +++++++++++++++++++++ 1 file changed, 100 insertions(+) create mode 100644 website/content/slides/04_parser_generators/_index.md 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 + +--- +# ? + -- cgit v1.3.1-26-gb76a