CS 326 Final Exam
finite automata: chars go into a lexer to make tokens
CFG/PDA: tokens go into parser to make AST
these then do other stuff - answers✔✔What is the lexer parser diagram?
Any arbitrary program fed to, lets call an analyzer, can it, with infinite memory and speed, determine if
the arbitrary program will stop sometime in the future? - answers✔✔What is the halting problem?
Symmetry in language design. - answers✔✔What is orthogonality?
statically typed and dynamically typed. - answers✔✔What are the two language "types"?
<assign> -> <var> = <expression> - answers✔✔What is Backus-Naur Form?
The process of breaking up symbols, typically text, into tokens. - answers✔✔What is lexing?
True - answers✔✔T/F. Regular grammars are finite automata.
- answers✔✔excercise: derive and parse tree
<program> —> begin <stmt_list> end
<stmt_list> <stmt> I <stmt> ; <stmt_list>
<stmt> —><var>=<expression>
<var>—>A I B I C
<expression> —> <var> + <var> | <var> - <var> | <var>
- answers✔✔excercise: derive and parse tree
, <assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <id> + <expr>
| <id> * <expr>
| (<expr>)
| <id>
When one input can produce two different outputs, i.e. parse trees. - answers✔✔What is ambiguity?
No, it is impossible to prove a grammar is not ambiguous, but one can prove a grammar is ambiguous by
finding an example. - answers✔✔Can you prove a grammar is not ambiguous?
LL: left to right, left-most derivation with no look ahead. - answers✔✔Define LL generator
GLR: generalized left-to-right. right-most derivation and handles some ambiguity. - answers✔✔Define
GLR generator
Adaptive LL*: allows some ambiguity in certain parts. Balances flexibility and speed. - answers✔✔Define
Adaptive LL* generator
Allows optional conditionals in grammar writing and recursion.
e -> (+ | -) term | term
T -> T [+ T] - answers✔✔What is EBNF?
e -> e (+ | -) term | term
term -> term (* | /) factor | factor
factor -> factor ^ exponent | id
exponent -> id
finite automata: chars go into a lexer to make tokens
CFG/PDA: tokens go into parser to make AST
these then do other stuff - answers✔✔What is the lexer parser diagram?
Any arbitrary program fed to, lets call an analyzer, can it, with infinite memory and speed, determine if
the arbitrary program will stop sometime in the future? - answers✔✔What is the halting problem?
Symmetry in language design. - answers✔✔What is orthogonality?
statically typed and dynamically typed. - answers✔✔What are the two language "types"?
<assign> -> <var> = <expression> - answers✔✔What is Backus-Naur Form?
The process of breaking up symbols, typically text, into tokens. - answers✔✔What is lexing?
True - answers✔✔T/F. Regular grammars are finite automata.
- answers✔✔excercise: derive and parse tree
<program> —> begin <stmt_list> end
<stmt_list> <stmt> I <stmt> ; <stmt_list>
<stmt> —><var>=<expression>
<var>—>A I B I C
<expression> —> <var> + <var> | <var> - <var> | <var>
- answers✔✔excercise: derive and parse tree
, <assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <id> + <expr>
| <id> * <expr>
| (<expr>)
| <id>
When one input can produce two different outputs, i.e. parse trees. - answers✔✔What is ambiguity?
No, it is impossible to prove a grammar is not ambiguous, but one can prove a grammar is ambiguous by
finding an example. - answers✔✔Can you prove a grammar is not ambiguous?
LL: left to right, left-most derivation with no look ahead. - answers✔✔Define LL generator
GLR: generalized left-to-right. right-most derivation and handles some ambiguity. - answers✔✔Define
GLR generator
Adaptive LL*: allows some ambiguity in certain parts. Balances flexibility and speed. - answers✔✔Define
Adaptive LL* generator
Allows optional conditionals in grammar writing and recursion.
e -> (+ | -) term | term
T -> T [+ T] - answers✔✔What is EBNF?
e -> e (+ | -) term | term
term -> term (* | /) factor | factor
factor -> factor ^ exponent | id
exponent -> id
