– integer arithmetic expressions with additions, subtraction, and multiplication operations
exp -> exp op exp | (exp) | number op -> + | - | *
BNF
• • • • • • •
Introduction
• Parsing is the task of determining the syntax, or structure, of a program. • It is also called syntax analysis. • The syntax of a programming language is usually given by the grammar rules of a context-free grammar. • The rules of context-free grammar are recursive. • Data structures representing the syntactic structure are also recursive – a parse tree or syntax tree.
The Parsing Process
parser Sequence of tokens
Syntax tree
• Usually, the sequence of tokens is not an explicit input parameter, but the parser calls a scanner procedure such as getToken to fetch the next token from the input as it is needed during the parser process.
Context-Free Grammar Rules
• Grammar rules are defined over an alphabet, or set of symbols.
– The symbols are usually tokens representing strings of characters.
Context-Free Grammar Rules (cont)
• The rule defines the structure whose name is to the left of the arrow. • The structure is defined to consist of one of the choices on the right-hand side separated by the vertical bars.
•
Context-free grammar rule consists of a string of symbols
1. Name for a structure. 2. Metasymbol ->. 3. A string of symbols
– Either a symbol from the alphabet – Or a name for a stinition CFL
• • • • A context-free grammar consists of the following: 1) A set T of terminals 2) A set N of nonterminals ( disjoint from T) 3) A set fo productions ,or grammer rles , of the form A a, where A is an element of N and a is an element of (T u N )* • 4) A start symbol S from the set N • A derivation over the grammer G is of the form S=>*w ,where w is belonged to T*.
Context-Free Grammars
• A context-free grammar is a specification for the syntactic structure of a programming language. • Context-free grammar involves recursive rules. • Example:
exp -> exp op exp | (exp) | number Names are written in italic. op -> + | - | * | - metasymbol for choice. Concatenation is used as a standard operation. No repetitions. -> is used to express the definitions of names. Regular expressions are used as components. The notation was developed by John Backus and adapted by Peter Naur. • The grammar rules in this form are said to be in Backus-Naur Form, or BNF.
The language generated by G
• The language ,written L(G) , is defined as the set L(G)= { w is belonged to T*| there exists a derivation S =>* w of G }