CSCE 434 Lecture 6

« previous | Monday, October 7, 2013 | next »

Optimizations

Reading code and spitting out lower abstraction happens more than one time.

This is a one-way street: generally can't go from lower level of abstraction to higher level.

Optimizations occur between the front and back end in several disjoint blocks

Scanning

Recall from lecture 4.

Flex is used to create scanners (and Bison parsers)

• by writing high level specifications
• The generated program code allows for the interpretation of this specification

Regular Expressions

(not perl-style REs, but "ideal" REs)

digit = (0|1|2|3|4|5|6|7|8|9)
integer = (+|-|)(0|(1|2|3|4|5|6|7|8|9)(digit)*)
decimal = integer . (digit)*

etc

Parsing

Recognizes a Context-Free syntax (c.f context-sensitive)

Can be used to guide context-sensitive analysis (storing information about variables, scope, etc)

Context Free Grammars

Backu-Naur Form

<sheep noise> ::= baa | baa <sheep noise>

Formally, a grammar consists of

• start symbol $S$
• set of non-terminal symbols $N$
• set of terminal symbols $T$
• set of productions/rewrite rules $P:N\to (N\cup T)$.

For Example:

1. <goal> ::= <expr>
2. <expr> ::= <expr> <op> <term>
3.          | <term>
4. <term> ::= number
5.          | id
6. <op> ::= +
7.        | -

• $S$ is <goal>
• $T$ is { number, id, +, - }
• $N$ is { <goal>, <expr>, <term>, <op> }
• $P$ is the rules above.

Sample parsing:

	<goal>
1	<expr>
2	<expr> <op> <term>
5	<expr> <op> y
7	<expr> - y
2	<expr> <op> <term> - y
4	<expr> <op> 2 - y
6	<expr> + 2 - y
3	<term> + 2 - y
5	x + 2 - y

The parser performs these transformations in reverse. The result (i.e. the order of rules applied) is called a parse, and can be represented as a parse tree or a syntax tree.

goal
`-- expr
    |-- expr
    |   |-- expr
    |   |   `-- term
    |   |       `-- <id,x>
    |   |-- op
    |   |   `-- +
    |   `-- term
    |       `-- <num,2>
    |-- op
    |   `-- -
    `-- term
        `-- <id,y>

Abstract Syntax Tree (AST) is much simpler and concise:

-
|-- +
|   |-- <id,x>
|   `-- <num,2>
`-- <id,y>

Note: The JVM is a stack-based machine, so it does not have any registers, only the top of the stack.