Archive Notes

3. Syntax

1 min read

Syntax

The syntax is concerned with the form of programs, it is given by:

  • an alphabet: set of characters that can be used
  • a set of rules: indicating how to form expressions, commands, etc
Link to original

Concrete Syntax

Concrete Syntax describes which chains of characters are well-formed programs.

Link to original

Abstract Syntax

Abstract Syntax describes the syntax trees, to which semantics is associated.

Link to original

Grammar

Grammar

To specify the syntax of a language, we define a grammar:

  • an alphabet, (terminals and non-terminals)
  • rules
  • initial symbol
Link to original

Terminals

Terminals are characters that may appear in the program.

Link to original

Non-terminals

Non-terminals are auxiliary components of the program.

Link to original

Backus-Naur Form

The Backus-Naur Form (BNF) is a common way to define a grammar.

Link to original

Example: concrete syntax

Below is an example of a concrete syntax in BNF:

Exp   ::= Num | Exp Op Exp
Op    ::= + | - | * | div
Num   ::= Digit | Digit Dum
Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The initial symbol is Exp The terminals are +, -, *, div, 0 … 9 The non-terminals are Exp, Op, Num, Digits

Example: abstract syntax

Below is an example of an abstract syntax in BNF:

e  ::= n | op(e,e)
op ::= + | - | * | div

This grammar defines trees and not strings, there is no ambiguity:

Abstract syntax describes program representation, it is not ambiguous, and we will always work with the abstract syntax of the language and study the semantics of the main constructs of the programming languages.

Graph View