Lexing

Regular Expressions

https://regex101.com/ https://regexr.com/

Parsing

I personally do not enjoy front end issues as much as back end. And yet a front to back compiler course starts there. Kind of off putting.

BNF Context Free Grammars Parsing Expression Grammar LL LALR

How do you get good error messages

sy brand paper on how compilter diagnostics could be imporved

Algorithms

List of algorithms - parsing Recursive Descent Earley parser Pratt Parser LL Parser LR Parser packrat allstar

Parser Combinators

String -> [(a,String)] A non deterministic search that consumes a prefix of the input. parsec

Alternative persecptive - each production is string position -> [nextposition]

Just making a parse tree acceptor vs something that outputs something.

Leermakers 1993- The functional treatement of parsing Memoizing parser combinators tabling

Parser Generators

Flex yacc/bison antlr Menhir error handling the new way Sam’s coq stuff https://github.com/slasser/AllStar https://github.com/slasser/CoStar

Semantic Actions

Shift Reduce Parsing

See Appell’s book https://en.wikipedia.org/wiki/Shift-reduce_parser

shift takes token off stream and puts onto stack reduce takes top of atxckc

Shift reduce conflicts