編譯原理-上下無關文法和文法分析(參考版)
2024-10-20 02:27本頁面
【正文】 typedef StreeNode * SyntaxTree。 struct streetnode * test, * thenpart, * elsepart。 ExpKind ekind。 typedef enum {IfK, OtherK} StmtKind。 typedef STreeNode * SyntaxTree Example statement ifstmt | other ifstmt if (exp) statement | if (exp) statement else statement exp 0 | 1 statement ifstmt if ( exp ) statement else statement 0 other other if (0) other else other if 0 other other Parse tree Syntax tree Example (cont) typedef enum {ExpK, StmtK} NodeKind。 int val。 Opkind op。 typedef enum {OpK, ConstK} ExpKind。Chapter 3 ContextFree Grammars and Parsing Instructor Jianhui Yue Software College SCU 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 contextfree grammar. ? The rules of contextfree 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. Sequence of tokens Syntax tree parser ContextFree Grammars ? A contextfree grammar is a specification for the syntactic structure of a programming language. ? Contextfree grammar involves recursive rules. ? Example: – integer arithmetic expressions with additions, subtraction, and multiplication operations exp exp op exp | (exp) | number op + | | * 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 ponents. ? The notation was developed by John Backus and adapted by Peter Naur. ? The grammar rules in this form are said to be in BackusNaur Form, or BNF. exp exp op exp | (exp) | number op + | | * Formal Definition CFL ? A contextfree 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 } ContextFree Grammar Rules ? Grammar rul
教學課件相關推薦
鄂ICP備17016276號-1