编译原理-上下无关文法和文法分析.ppt

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 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 Grammars A context-free grammar is a specification for the syntactic structure of a programming language. Context-free grammar involves recursive rules. Example: integer arithmetic expressions with additions, subtraction, and multiplication operations BNF Names are written in italic. | - 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. Formal Definition 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*. 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 } 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 rule consists of a string of symbols Name for a