Syntax

1. Any programming language needs precise definition of the syntax

• When Algol was developed there was a major disagreement about what they agreed on
• meta-languages define languages

1. Different ways of describing a language

• Tutorial approach: Explain using examples
• Reference manual type of approach use meta-language to describe the syntax and English to describe the semantics
• Formal specifications: Don't use English. Use symbols and notations to specify syntax as well as semantics

1. Expressions

• Prefix notations
  • operator followed by the operand
  • * 6 7
  • * 6 + 8 9
  • are best evaluated using an expression tree
• Postfix notations
  • operands followed by the operator
  • 6 7 *
  • 6 8 9 + *
  • are best evaluated using a stack
• Infix notations
  • operator is in between the operands
  • unary operators such as - have to be treated differently
  • precedence and associativity
  • 4 - 2 - 1 (left associative)
  • 4 + 2 * 8 (precedence of * over +)
  • Infix notations are used because we are familiar with them
  • You generally use mixfix notations
  • (- b + sqrt(b*b - 4 * a * c))/(2 * a)
• Generally, the programming languages use the syntax that is most easy to read

1. Abstract syntax trees (2.2)

• Use meaningful components to draw the syntax trees
• General format of the tree is given at the bottom of page 31
• Figure on top of page 33 shows how an operator with three operands can be represented using an expression tree

1. Lexical syntax

• Tokens are similar to the words
  • dot and dote may not be related to each other
  • similarly < and <> don't have to have any relationship with each other

1. Context free grammars

• All the grammars that can be described by BNF (Backus-Naur Form) are context free grammars
• Conversely, any context free language can be described by the BNF
• BNF
  • Terminals or tokens: Meaning is self-evident
  • Non-terminal symbols generally enclosed in angled brackets such as <expression>
  • Productions that define the non-terminal symbols
  • Generally a starting non-terminal defined by the first production such as <program>
• Example: Fig. 2.3
  • <real-number> is the starting non-terminal
  • other non-terminals include <integer-part>, <fraction>, <digit>,
  • terminals include 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and .
  • A non-terminal symbol is defined using ::= (read as defined as), | is used as the or operator