inc, cond, a, etc. 3. Booleans: true and false 4. Single-argument anonymous functions: fn a => a 5. Function application: inc 42 6. If expressions: if cond then t else f Vehicle Language: µML
inc, cond, a, etc. 3. Booleans: true and false 4. Single-argument anonymous functions: fn a => a 5. Function application: inc 42 6. If expressions: if cond then t else f 7. Addition and subtraction: a + b, a - b Vehicle Language: µML
inc, cond, a, etc. 3. Booleans: true and false 4. Single-argument anonymous functions: fn a => a 5. Function application: inc 42 6. If expressions: if cond then t else f 7. Addition and subtraction: a + b, a - b 8. Parenthesized expressions: (a + b) Vehicle Language: µML
=> a ) 2 Parser uage • Expects a stream of characters or bytes • Groups them into semantically atomic units: tokens! • These are the words of the language! • What are the rules for grouping them, though?
These rules form the lexical grammar • Can be defined using regular expressions • Conducive to easy and efficient implementations • Using a RegExp library Lexing
These rules form the lexical grammar • Can be defined using regular expressions • Conducive to easy and efficient implementations • Using a RegExp library • By hand isn't hard either, just a little cumbersome Lexing
These rules form the lexical grammar • Can be defined using regular expressions • Conducive to easy and efficient implementations • Using a RegExp library • By hand isn't hard either, just a little cumbersome • Lexer generators: Lex, Flex, Alex, ANTLR, etc. Lexing
These rules form the lexical grammar • Can be defined using regular expressions • Conducive to easy and efficient implementations • Using a RegExp library • By hand isn't hard either, just a little cumbersome • Lexer generators: Lex, Flex, Alex, ANTLR, etc. • Lexing is what you need for syntax definition files Lexing
Not all combinations of valid words form valid phrases in a language • Syntactically correct: val a = 1 • Syntactically incorrect: val val val • We must define the structure of phrases Parsing
Not all combinations of valid words form valid phrases in a language • Syntactically correct: val a = 1 • Syntactically incorrect: val val val • We must define the structure of phrases • A syntactical grammar achieves that Parsing
recognize nested structures • Because they use a finite amount of memory • Nesting needs a stack to remember the upper structures you're traversing Parsing
recognize nested structures • Because they use a finite amount of memory • Nesting needs a stack to remember the upper structures you're traversing • Syntactical grammars express nesting using recursion Parsing
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr oper = + | - bool = true | false Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr oper = + | - bool = true | false Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
) | fn var => expr | if expr then expr else expr | let val var = expr in expr end | expr oper expr | expr expr bool = true | false oper = + | - Here, blue symbols represent tokens coming from the lexer, not keywords. µML — Syntactical Grammar
ML • double 1 + 2 = (double 1) + 2 • double 1 + 2 ≠ double (1 + 2) • A rule's alternatives don't encode precedence • Grammars convey this by chaining rules in order of precedence • Doesn't scale with many infix operators • Use a special parser for that, e.g., the Shunting Yard algorithm Introducing Precedence
root • Bottom-up parsing: builds tree from the leaves • Top-down is easy to write by hand • Bottom-up is not, but it's used by generators Parsing Strategies
root • Bottom-up parsing: builds tree from the leaves • Top-down is easy to write by hand • Bottom-up is not, but it's used by generators • Parser generators: YACC, ANTLR, Bison, etc. Parsing Strategies
Builds the tree top to bottom, from root to leaves, hence Descent • Parallels the structure of the grammar • Main idea: each grammar production becomes a function Recursive Descent Parser
Builds the tree top to bottom, from root to leaves, hence Descent • Parallels the structure of the grammar • Main idea: each grammar production becomes a function • Recursion in the grammar translates to recursion in the code, hence Recursive Recursive Descent Parser
Builds the tree top to bottom, from root to leaves, hence Descent • Parallels the structure of the grammar • Main idea: each grammar production becomes a function • Recursion in the grammar translates to recursion in the code, hence Recursive • Recursion is the main difference compared to regexes; it needs a stack Recursive Descent Parser
Builds the tree top to bottom, from root to leaves, hence Descent • Parallels the structure of the grammar • Main idea: each grammar production becomes a function • Recursion in the grammar translates to recursion in the code, hence Recursive • Recursion is the main difference compared to regexes; it needs a stack • Very popular, e.g., Clang uses it for C/C++/Obj-C Recursive Descent Parser
Builds the tree top to bottom, from root to leaves, hence Descent • Parallels the structure of the grammar • Main idea: each grammar production becomes a function • Recursion in the grammar translates to recursion in the code, hence Recursive • Recursion is the main difference compared to regexes; it needs a stack • Very popular, e.g., Clang uses it for C/C++/Obj-C • Parser combinators are an abstraction over this idea Recursive Descent Parser
only a problem for our current parsing strategy; others can easily cope with it • The problem is that some rules are left-recursive, i.e., the rule itself appears as the first symbol on the left Removing Left-Recursion
only a problem for our current parsing strategy; others can easily cope with it • The problem is that some rules are left-recursive, i.e., the rule itself appears as the first symbol on the left • This is problematic for a recursive descent parser because the structure of function calls follow the structure of rule definitions Removing Left-Recursion
only a problem for our current parsing strategy; others can easily cope with it • The problem is that some rules are left-recursive, i.e., the rule itself appears as the first symbol on the left • This is problematic for a recursive descent parser because the structure of function calls follow the structure of rule definitions • That means infinite recursion in the parser, which isn't good Removing Left-Recursion
SiteGround - Reliable hosting with speed, security, and support you can count on.
igstan
yui_knk
chiroruxx
k1mu21
rkaga
mayuki
kawayu
javiergs
licux
jinwatanabe
ternbusty
syumai
minodriven
skoyamalab
reverentgeek
akihiro_kokubo
csswizardry
addyosmani
kevinliebholz
watany
tammyeverts
samlambert
ryanjones
colly
![µML — Lexical Grammar integers 0|[1-9][0-9]* identifiers [a-zA-Z]+ symbols (,](https://files.speakerdeck.com/presentations/230b8676fc7b46cba354f95edd7fee01/slide_65.jpg){kind=link}
![integers 0|[1-9][0-9]* identifiers [a-zA-Z]+ symbols (, ), +, -, =,](https://files.speakerdeck.com/presentations/230b8676fc7b46cba354f95edd7fee01/slide_66.jpg){kind=link}
![integers 0|[1-9][0-9]* identifiers [a-zA-Z]+ symbols (, ), +, -, =,](https://files.speakerdeck.com/presentations/230b8676fc7b46cba354f95edd7fee01/slide_67.jpg){kind=link}
![integers 0|[1-9][0-9]* identifiers [a-zA-Z]+ symbols (, ), +, -, =,](https://files.speakerdeck.com/presentations/230b8676fc7b46cba354f95edd7fee01/slide_68.jpg){kind=link}
![integers 0|[1-9][0-9]* identifiers [a-zA-Z]+ symbols (, ), +, -, =,](https://files.speakerdeck.com/presentations/230b8676fc7b46cba354f95edd7fee01/slide_69.jpg){kind=link}
