Syntax

Part 2

Andreas Stefik

This Lesson is our second related to "Processing" programming languages

• We will discuss operator precedence and how languages can take this into account
• We will be skipping some of the formalism related to semantics for now, but will come back to it later in the course
• Our primary addition with this second less is on practicing more parse trees, especially as they relate to associativity and and precedence

We need to account for Operator Precedence with our Grammars

• How you account for operator precedence depends in part on what kind of grammar generator you are using
• We are practicing this "in theory" with something like BNF
• We are doing theory first because it is harder to understand. Antlr is likely easier
• It is also a common way to describe these things in textbooks
• Plus, not all grammar generators are as easy to understand as Antlr, so it helps to understand how it used to be done.
• We will move to more practical ways of handling these issues in your later assignments

​

Consider the following Unambiguous Grammar for Expressions

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> + <term>

| <term>

​

<term> → <term> * <factor>

| <factor>

<factor> → ( <expr>)

| <id>

• This is an assignment statement with properties like
• Only three possible variables
• Multiplication and addition
• Parentheses
• Notice the way expressions are structured, with intermediary rules like "term" and "factor

Group Project 1:Develop a derivation and a Parse tree for the string

​

A = B + C * A

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> + <term>

| <term>

​

<term> → <term> * <factor>

| <factor>

<factor> → ( <expr>)

| <id>

Let's discuss this Parse Tree

How do we Handle Associativity?

• This is left associative for plus
• Notice the B and C are lower in the tree then the A, which is the idea
• We can define grammars for right associativity as well, although this is less common

Group Project 2: Create a Parse Tree with the following input

​

A ** B

<factor> → <expr> ** <factor>

| <expr>

<expr> → ( <factor> )

| <id>

<id> → A | B | C

There are Extensions to BNF Grammars

• This is an optional part of a rule

<if_stmt> →if (<expression>) <statement> [else <statement>]

• This allows indefinite repetition

<ident_list> →<identifier> {, <identifier> }

• This is another common shorthand

<term> → <term> (* | / | % ) <factor>

​

Group Project 3: Create an EBNF Grammar for +, -, *, /, and ^ (exponentiation). Then derive a parse tree.

​

a + (b * c) ^ 5 - 4

Summary

• There are many other important aspects of programming languages in relation to syntax and semantics
• For now, though, we between these two lectures/group assignments, we have now discussed
• Grammars
• Derivations
• Parse Trees
• Handling associativity and precedence
• We have not yet handled much about semantics, and will later, but for now just recognize there is a lot of processing that has to take place beyond the use of grammars