TINY语法分析

1、TINY语言语法分析一、两个预测语法分析需要的知识.1.上下文无关文法及其处理上下文无关文法是描述语法的工具，如中提供了TINY文法，用大写字符表示非终结符，小写字符和符号表示终结符($ 表示空) ，$表示空集，#表示记号结束。BNF of the TINY*PROGRAM- STMT-SEQUENCESTMT-SEQUENCE- STMT-SEQUENCE ; STATEMENT | STATEMENTSTATEMENT- IF-STMT | REPEAT-STMT | ASSIGN-STMT | READ-STMT | WRITE-STMTIF-STMT- if EXP then STMT

2、-SEQUENCE end | if EXP then STMT-SEQUENCE else STMT-SEQUENCE endREPEAT-STMT- repeat STMT-SEQUENCE until EXPASSIGN-STMT- identifier := EXPREAD-STMT- read identifierWRITE-STMT- write EXPEXP- SIMPLE-EXP COMPARISON-OP SIMPLE-EXP | SIMPLE-EXPCOMPARISON-OP- SIMPLE-EXP ADDOP TERM | TERMADDOP- + | -TERM- TE

3、RM MULOP FACTOR |FACTORMULOP- * | /FACTOR- ( EXP ) | number | identifier2.对文法进行处理文法中存在二义性, 左递归和公因子对于二义性不同的文法视具体情况而论.消除左递归(龙书中的例子):A- Aa | b消除后的产生式A- b A A- aA | $消除左递归的方法是:A- Aa1| Aa2| | Aam| b1| b2| | bn (其中bi都不已A开头)使用一下产生式替换A- b1A| b2A | | bnAA- a1A | a2A| | amA | $看上面的BNF 其中有几条产生式是属于左递归的例子:STMT-S

4、EQUENCE- STMT-SEQUENCE ; STATEMENT|STATEMENTSIMPLE-EXP- SIMPLE-EXP ADDOP TERM |TERMTERM- TERM MULOP FACTOR |FACTOR按照消除左递归的方法变换成下面的产生式STMT-SEQUENCE- STATEMENTSTMT-SEQUENCESTMT-SEQUENCE- ; STATEMENTSTMT-SEQUENCE|$SIMPLE-EXP- TERMSIMPLE-EXPSIMPLE-EXP- ADDOP TERMSIMPLE-EXP|$TERM- FACTORTERMTERM- MULOP F

5、ACTORTERM|$提取公因子(龙书中的例子):A- a b1|a b2提取公因子后:A- aAA- b1|b2提取公因子的方法是:A- a b1| a b2| | a bn| c (c是不以a开头的候选式)提取后:A- aA | cA- b1| b2| | bn上面的BNF 中有几条公因子的例子:IF-STMT- if EXP then STMT-SEQUENCE end | ifEXPthenSTMT-SEQUENCEelseSTMT-SEQUENCEendEXP- SIMPLE-EXP COMPARISON-OP SIMPLE-EXP|SIMPLE-EXP提取公因子后:IF-STMT-

6、 if EXP then STMT-SEQUENCE ELSE-STMTendELSE-STMT- elseSTMT-SEQUENCE|$EXP- SIMPLE-EXP EXPEXP- COMPARISON-OP SIMPLE-EXP|$所以处理后的BNF文法为BNF of the TINY*PROGRAM- STMT-SEQUENCESTMT-SEQUENCE- STATEMENT STMT-SEQUENCESTMT-SEQUENCE- ; STATEMENT STMT-SEQUENCE | $STATEMENT- IF-STMT | REPEAT-STMT | ASSIGN-STMT| R

7、EAD-STMT | WRITE-STMTIF-STMT- if EXP then STMT-SEQUENCE ELSE-STMT endELSE-STMT- else STMT-SEQUENCE | $REPEAT-STMT- repeat STMT-SEQUENCE until EXPASSIGN-STMT- identifier := EXPREAD-STMT- read identifierWRITE-STMT- write EXPEXP- SIMPLE-EXP EXPEXP- COMPARISON-OP SIMPLE-EXP | $COMPARISON-OP- TERM SIMPLE

8、-EXPSIMPLE-EXP- ADDOP TERM SIMPLE-EXP | $ADDOP- + | -TERM- FACTOR TERMTERM- MULOP FACTOR TERM | $MULOP- * | /FACTOR- ( EXP ) | number | identifier3.first集合和follow集合进行语法分析时, 非终结符的产生式会包含很多候选式, 当遇到一个记号, 用哪个候选式来扩展就成了问题. 当我们知道了候选式对应的第一个终结符时就可以确定了.first集合就是文法产生式中所有的候选式的第一个终结符的集合.(参考)使用如下方法来就文法的first集合(参考龙

9、书):(1). 如果X是终结符, first(X) = X(2). 如果X- $ 是产生式, 则将$ 加入first(X)(3). 如果X是非终结符, 且X- Y1Y2Yk是产生式, 则: 1).若对于某个i, 有a 属于first(Yi), 且$属于first(Y1)first(Yi-1), 则 a属于first(X) 2).若对于j = 1, 2, , k 有$属于first(Yj) 则$ 属于first(X)龙书上的例子:E- TEE- +TE | $T- FTT- *FT | $F- (E) | id对于first(E), E是非终结符, 根据(3)的1) 当i = 1时. T前面没有

10、符号了所以first(T)属于first(E), 同理first(F) 属于first(T). 又根据(1), first(F) = (, id, $ 不属于first(F), 所以first(F) = first(T) = first(E) = (, id.根据(1),(2), 的first(E) = +, $, first(T) = *, $根据求first集合的规则和TINY的BNF求出TINY的first集合为:first(PROGRAM) = first(STMT-SEQUENC) = first(STATEMENT) =if, repeat, identifier, read, w

11、ritefirst(STMT-SEQUENCE) = ;,$first(IF-STMT) = iffirst(ELSE-STMT) = else,$first(REPEAT-STMT) = repeatfirst(ASSIGN-STMT) = identifierfirst(READ-STMT) = readfirst(WRITE-STMT) = writefirst(EXP) = first(SIMPLE-EXP) = first(TERM) = first(FACTOR) =(, number, identifierfirst(EXP) = , =,$first(COMPARISON-OP

12、) = aBb 则将first(b)中除了$ 以外的符号加入到follow(B)中.(3). 如果存在产生式A- aB, 或A- aBb且$ 属于first(b),则 将follow(A)加入到follow(B)中.龙书中的例子:E- TEE- +TE | $T- FTT- *FT | $F- (E) | id对于follow(E), 根据(1), follow(E) = #, 在产生式右部包含E的产生式F- (E) | id 其中根据(2)是的)加入到follow(E)中, 所以follow(E) = ), #.对于follow(E), 观察所有右部包含E的产生式: E- TE和E- +TE

13、 | $ 在每一个产生式中E都处在右部最右端所以根据(3), 右follow(E)属于follow(E) 所以follow(E) = follow(E).对于follow(T), 观察所有右部包含T的产生式E- TE和E- +TE | $ 根据(2)first(E)中处理$ 以外的符号都属于follow(T), 所以follow(T) = +, 又$ 属于first(E) 根据(3)有follow(E) 和 follow(E) 都属于follow(T), 但是follow(E) = follow(E)不用重复加入. 所以follow(T) = +, ), #同上follow(T) = foll

14、ow(T)同上follow(F) = *, +, ), #根据求follow集合的规则和TINY的BNFfollow(PROGRAM) = #follow(STMT-SEQUENCE) = #, else, end, untilfollow(STMT-SEQUENCE) = #, else, end, untilfollow(STATEMENT) = follow(IF-STMT) = follow(REPEAT-STMT) =follow(ASSIGN-STMT) = follow(READ-STMT) = follow(WRITE-STMT) =;, #, else, end, until

15、follow(ELSE-STMT) = endfollow(EXP) = then, ), ;, #, else, end, untilfollow(EXP) = follow(EXP)follow(COMPARISON-OP) = (, number, identifierfollow(SIMPLE-EXP) = , =, then, ), ;, #, else, end, untilfollow(SIMPLE-EXP) = follow(SIMPLE-EXP)follow(TERM) = +, -, , =, then, ), ;, #, else, end, untilfollow(AD

16、DOP) = (, number, identifierfollow(TERM) = follow(TERM)follow(MULOP) = (, number, identifierfollow(FACTOR) = *, /, +, -, a)(1)如$ 不属于first(A)则 select(A- a) = first(A)(2)如$ 属于first(A) 则 select(A- a) = first(A) U follow(A)根据select集合的规则和TINY的BNFselect(PROGRAM- STMT-SEQUENCE) = if, repeat, identifier, re

17、ad, writeselect(STMT-SEQUENCE- STATEMENT STMT-SEQUENCE) =if, repeat, identifier, read, writeselect(STMT-SEQUENCE- ; STATEMENT STMT-SEQUENCE) = ;select(STMT-SEQUENCE-$) = #, else, end, untilselect(STATEMENT- IF-STMT) = ifselect(STATEMENT- REPEAT-STMT) = repeatselect(STATEMENT- ASSIGN-STMT) = identifi

18、erselect(STATEMENT- READ-STMT) = readselect(STATEMENT- WRITE-STMT) = writeselect(IF-STMT- if EXP then STMT-SEQUENCE ELSE-STMT end) = ifselect(ELSE-STMT- else STMT-SEQUENCE) = elseselect(ELSE-STMT-$) = endselect(REPEAT-STMT- repeat STMT-SEQUENCE until EXP) = repeatselect(ASSIGN-STMT- identifier := EX

19、P) = identifierselect(READ-STMT- read identifier) = readselect(WRITE-STMT- write EXP) = writeselect(EXP- SIMPLE-EXP EXP) = (, number, identifierselect(EXP- COMPARISON-OP SIMPLE-EXP) = $) = then, ), ;, #, else, end, untilselect(COMPARISON-OP- ) = =) = =select(SIMPLE-EXP- TERM SIMPLE-EXP) = (, number,

20、 identifierselect(SIMPLE-EXP- ADDOP TERM SIMPLE-EXP) = +, -select(SIMPLE-EXP-$) = +) = +select(ADDOP- -) = -select(TERM- FACTOR TERM) = (, number, identifierselect(TERM- MULOP FACTOR TERM) = *, /select(TERM-$) = +, -, *) = *select(MULOP- /) = /select(FACTOR- (EXP) = (select(FACTOR- number) = numbers

21、elect(FACTOR- identifier) = identifier二、递归预测语法分析1.分析程序 “预测”并不准确, 因为通过上面的select集合，我们知道了当前状态下输入一个记号该如何选中产生式的候选式。这个程序完全是依照select集合来构造的. 如何根据select集合来构造程序呢.看两个例子(这里的语法分析程序与中tiny语法分析程序完全不同):对于select(STMT-SEQUENCE- STATEMENT STMT-SEQUENCE) =if, repeat, identifier, read, write我们可以构造出程序(这里的for(;)和check_inpu

22、t都是错误处理程序)static void parse_stmt_sequence(void) for(;) switch(token) case KEY_IF: case KEY_REPEAT: case KEY_READ: case KEY_WRITE: case ID: parse_statement(); parse_stmt_sequence_(); return; break; default: if(check_input(stmt_sequence_first, STMT_SEQUENCE_FIRST_COUNT, stmt_sequence_follow, STMT_SEQU

23、ENCE_FOLLOW_COUNT) != IN_FIRST_SET) return; break; select集合的意思是当在分析STMT-SEQUENCE时, 当输入记号为if, repeat, identifier, read, write时我们就转换到STATEMENT和STMT-SEQUENCE的分析程序中. 如果不是如上的这些记号则表示当前分析的程序有错误, 要进行错误处理.有两条select集合select(STMT-SEQUENCE- ; STATEMENT STMT-SEQUENCE) = ;select(STMT-SEQUENCE-$) = #, else, end, u

24、ntil都是关于STMT-SEQUENCE的所以, 我们将它们放到一个函数中 如下:static void parse_stmt_sequence_(void) switch(token) case SEMI: match(SEMI); parse_statement(); parse_stmt_sequence_(); break; case KEY_ELSE: case KEY_END: case KEY_UNTIL: case END_FILE: /* - $ */ break; default: /* dropp the SEMI symbol */ syntax_error(want

25、 symbol, ;); parse_statement(); parse_stmt_sequence_(); break; 当处理STMT-SEQUENCE的分析时, 输入记号时;时程序转入; STATEMENT STMT-SEQUENCE状态分析序列. match(SEMI);是对终结符;匹配过程, 其中包含了错误处理的过程. 当输入记号为#, else, end, until中的一个时对应的产生式为STMT-SEQUENCE-$ 这表示这个分析过程什么也没做. 所以直接退出到上一级分析程序中.所以由上面的select集合可以构造出语法分析程序(包含错误处理和对语法树的构造):/* imp

26、lement of parse for TINY compiler* Now this isnt build abstrict syntax tree*/#include globals.h#include util.h#include scan.h#include parse.h#include parse_set.h/* The token for get_token */static TokenType token;/* local utility functios */static void syntax_error(const char* err, const char* token

27、_str);static void match(TokenType match_token);static int check_input(const TokenType* first, int first_count, const TokenType* follow, int follow_count);static TreeNode* new_stmt_node(StmtKind kind);static TreeNode* new_exp_node(ExpKind kind);static char* copy_string(const char* str);/* local parse

28、 functions */static TreeNode* parse_stmt_sequence(void);static TreeNode* parse_statement(void);static TreeNode* parse_stmt_sequence_(void);static TreeNode* parse_if_stmt(void);static TreeNode* parse_else_stmt(void);static TreeNode* parse_repeat_stmt(void);static TreeNode* parse_assign_stmt(void);sta

29、tic TreeNode* parse_read_stmt(void);static TreeNode* parse_write_stmt(void);static TreeNode* parse_exp(void);static TreeNode* parse_exp_(void);static TreeNode* parse_simple_exp(void);static TreeNode* parse_simple_exp_(void);static TreeNode* parse_comparison_op(void);static TreeNode* parse_term(void)

30、;static TreeNode* parse_term_(void);static TreeNode* parse_addop(void);static TreeNode* parse_mulop(void);static TreeNode* parse_factor(void);/* The implement of parse for TINY*/TreeNode* parse(void) TreeNode* tree = NULL; token = get_token(); for(;) switch(token)case KEY_IF:case KEY_REPEAT:case KEY

31、_READ:case KEY_WRITE:case ID: tree = parse_stmt_sequence(); match(END_FILE); return tree; break;default: if(check_input(program_first, PROGRAM_FIRST_COUNT, program_follow, PROGRAM_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; /* local parse functions */static TreeNode* parse_stmt_sequence(void)

32、 TreeNode* tree = NULL; TreeNode* sibling_tree = NULL; for(;) switch(token)case KEY_IF:case KEY_REPEAT:case KEY_READ:case KEY_WRITE:case ID: tree = parse_statement(); sibling_tree = parse_stmt_sequence_(); if(tree = NULL) tree = sibling_tree; else tree-sibling = sibling_tree; return tree; break;defa

33、ult: if(check_input(stmt_sequence_first, STMT_SEQUENCE_FIRST_COUNT, stmt_sequence_follow, STMT_SEQUENCE_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_statement(void) TreeNode* tree = NULL; for(;) switch(token)case KEY_IF: tree = parse_if_stmt(); return tree; break;case KE

34、Y_REPEAT: tree = parse_repeat_stmt(); return tree; break;case ID: tree = parse_assign_stmt(); return tree; break;case KEY_READ: tree = parse_read_stmt(); return tree; break;case KEY_WRITE: tree = parse_write_stmt(); return tree; break;default: if(check_input(statement_first, STATEMENT_FIRST_COUNT, s

35、tatement_follow, STATEMENT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_stmt_sequence_(void) TreeNode* tree = NULL; TreeNode* sibling_tree = NULL; for(;) switch(token)case SEMI: match(SEMI); tree = parse_statement(); sibling_tree = parse_stmt_sequence_(); if(tree = NULL)

36、 tree = sibling_tree; else tree-sibling = sibling_tree; return tree; break;case KEY_ELSE:case KEY_END:case KEY_UNTIL:case END_FILE: /* - $ */ return tree; break;default: if(check_input(stmt_sequence_first, STMT_SEQUENCE_FIRST_COUNT, stmt_sequence_follow, STMT_SEQUENCE_FOLLOW_COUNT) != IN_FIRST_SET)

37、return tree; break; static TreeNode* parse_if_stmt(void) TreeNode* tree = NULL; for(;) switch(token)case KEY_IF: tree = new_stmt_node(KIND_IF); match(KEY_IF); if(tree != NULL) tree-child0 = parse_exp(); match(KEY_THEN); if(tree != NULL) tree-child1 = parse_stmt_sequence(); tree-child2 = parse_else_s

38、tmt(); match(KEY_END); return tree; break;default: if(check_input(if_stmt_first, IF_STMT_FIRST_COUNT, if_stmt_follow, IF_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_else_stmt(void) TreeNode* tree = NULL; for(;) switch(token)case KEY_ELSE: match(KEY_ELSE); tree = pa

39、rse_stmt_sequence(); return tree; break;case KEY_END: /* - $ */ return tree; break;default: if(check_input(else_stmt_first, ELSE_STMT_FIRST_COUNT, else_stmt_follow, ELSE_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_repeat_stmt(void) TreeNode* tree = NULL; for(;) swi

40、tch(token)case KEY_REPEAT: tree = new_stmt_node(KIND_REPEAT); match(KEY_REPEAT); if(tree != NULL) tree-child0 = parse_stmt_sequence(); match(KEY_UNTIL); if(tree != NULL) tree-child1 = parse_exp(); return tree; break;default: if(check_input(repeat_stmt_first, REPEAT_STMT_FIRST_COUNT, repeat_stmt_foll

41、ow, REPEAT_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree;break; static TreeNode* parse_assign_stmt(void) TreeNode* tree = NULL; for(;) switch(token)case ID: tree = new_stmt_node(KIND_ASSIGN); if(tree != NULL) = copy_string(token_string); match(ID); match(ASSIGN); if(tree != NULL) tr

42、ee-child0 = parse_exp(); return tree; break;default: if(check_input(assign_stmt_first, ASSIGN_STMT_FIRST_COUNT, assign_stmt_follow, ASSIGN_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_read_stmt(void) TreeNode* tree = NULL; for(;) switch(token)case KEY_READ: tree = n

43、ew_stmt_node(KIND_READ); match(KEY_READ); if(tree != NULL) = copy_string(token_string); match(ID); return tree; break;default: if(check_input(read_stmt_first, READ_STMT_FIRST_COUNT, read_stmt_follow, READ_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_w

44、rite_stmt(void) TreeNode* tree = NULL; for(;) switch(token)case KEY_WRITE: tree = new_stmt_node(KIND_WRITE); match(KEY_WRITE); if(tree != NULL) tree-child0 = parse_exp(); return tree; break;default: if(check_input(write_stmt_first, WRITE_STMT_FIRST_COUNT, write_stmt_follow, WRITE_STMT_FOLLOW_COUNT) != IN_FIRST_SET) return tree; break; static TreeNode* parse_exp(void) TreeNode* tree = NULL; TreeNode* tree_op = NULL; for(;) switch(token)case LPAREN:case NUM:case ID: tree = parse_simple_exp(); tree_op = parse_exp_(); if(tree_op != NULL) tree_op-child0 = tr