Compiler: Difference between revisions
Jump to navigation
Jump to search
| Line 77: | Line 77: | ||
= Resource = | = Resource = | ||
* coursera.org | * [https://class.coursera.org/compilers-004/ coursera.org] | ||
Revision as of 17:18, 26 November 2014
Lexical Analysis
if (i == j)
z = 0;
else
z = 1;
is indeed below in computers
\tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1;
An implementation must do
- Recognize substrings corresponding to tokens
- Identify the token class of each lexeme
Token Class
Identifier, keywords, '(', ')', Numbers, ...
- Token classes correspond to sets of strings.
- Identifier: A1, Foo, B17
- Integer: 0, 99
- Keyword: 'else' or 'if' or 'begin' or ...
- Whitespace: if___else
For the last code example, the tokens are: if, whitespace, (, i, == , j, \t, \n, else, z, =, 1, ;
Token string ---> Lexical Analysis -------> Parser
Regular Languages
Regular expressions specify regular languages.
Five constructs
- Two base cases - empty and 1-character strings
- Three compound expressions - union, concatenation, iteration.
Finite Automata
- Regular expressions = specification
- Finite automata = implementation
A finite automaton consists of
- input alphabet
- set of states
- start state
- set of accepting states
- set of transitions
Parsing
| Input | Ouput | |
|---|---|---|
| Lexer | Strings of characters | Strings of tokens |
| Parser | String of tokens | Parse tree |
Context-Free Grammars (CFG)
Parser must distinguish between valid and invalid strings of tokens.
Programming languages have recursive structure.