[第14讲-语法分析-9.ppt

中国科大 编译原理和技术 大连理工软件学院 胡 彦 huyan.ssdut@ 加点项的意义 文法 加点项的意义 代表的含义 加点项的意义 代表的含义 加点项的意义 代表的含义 可能的加点语法树 重新示范一下 加点的语法树 重新示范一下 重新示范一下 重新示范一下 重新示范一下 LR分析的特点 LR分析方法的特点 栈中的文法符号总是形成一个活前缀。 LR分析的特点 LR分析的特点 LR分析方法的特点 栈中的文法符号总是形成一个活前缀。 分析表的转移函数本质上是识别活前缀的DFA。 LR分析的特点 例 E ? E + T | E ? T T ? T * F | T ? E F ? (E ) | F ? id LR分析的特点 LR分析方法的特点 栈中的文法符号总是形成一个活前缀。 分析表的转移函数本质上是识别活前缀的DFA。 栈顶的状态符号包含了确定句柄所需要的一切信息。 当通过当前状态S和当前输入终结符a查ACTION表得到的表项ACTION[S,a]=ri时，说明栈中已经有句柄形成 LR分析的特点 LR分析方法的特点 栈中的文法符号总是形成一个活前缀。 分析表的转移函数本质上是识别活前缀的DFA。 栈顶的状态符号包含了确定句柄所需要的一切信息。 能分析的文法类是预测分析法能分析的文法类的真超集。 3.7 分析器的生成器 3.7.1 分析器的生成器Yacc 3.7 分析器的生成器 Yacc的实现是以LALR分析方法作为基本的原理 Yacc程序包括三个部分 声明 ％％ 翻译规则 ％％ 支持例程 例---声明部分 %{ #include ctype.h /* 常量、变量的声明*/ %} %token DIGIT %% 例---翻译规则部分 line : expr ‘\n’ {printf(“%d\n”, $1);} ; expr : expr ‘+’ term {$$ = $1+$3;} | term ; term : term ‘*’ factor {$$ = $1 * $3;} | factor ; factor : ’(’ expr ‘)’ {$$ = $2;} | DIGIT ; %% 例---支持例程部分 yylex(){ int c; c = getchar(); if (isdigit(c)){ yylval = c – ‘0’; return DIGIT; } return c; } 3.7 分析器的生成器 3.7.2 用Yacc处理二义文法 解决分析动作冲突的两大默认规则： 对于归约-归约冲突，选择在Yacc 程序中最先出现的那个产生式归约 对于移进-归约冲突，优先移进 3.7 分析器的生成器 3.7.2 用Yacc处理二义文法 例 台式计算器 输入一个表达式并回车，显示计算结果。 也可以输入一个空白行。 3.7 分析器的生成器 %{ # include ctype .h # include stdio.h # define YYSTYPE double /* 将栈定义为double类型 */ %} ? %token NUMBER %left ‘+’ ‘?’ %left ‘*’ ‘/ ’ %right UMINUS %% 3.7 分析器的生成器 lines : lines expr ‘\ n’ {printf ( “%g \ n”, $2 ) } | lines ‘\ n’ | /* ? */ ; expr : expr ‘+’ expr {$$ = $1 + $3; } | expr ‘?’ expr {$$ = $1 ? $3; } | expr ‘*’ expr {$$ = $1 * $3; } | expr ‘/ ’ expr {$$ = $1 / $3; } | ‘(’ expr ‘)’ {$$ = $2; } | ‘?’ expr %prec UMINUS {$$ = ?$2; } | NUMBER ; %% 3.7 分析器的生成器 yylex ( ) { int c; while ( ( c = getchar ( ) ) = = ‘ ’ ); if ( ( c = = ‘.’ ) | | (isdigit (c) ) ) { ungetc (c, stdin); scanf ( “% lf ”, yylval); return NUMBER; } retu