第91集：二义性文法的处理

核心知识点讲解

二义性文法的概念

二义性文法是指存在至少一个句子可以通过不同的最左推导或最右推导生成不同的语法树的文法。换句话说，二义性文法对于同一个输入可能有多种不同的解析方式。

示例：简单表达式文法

expr → expr + expr
     | expr * expr
     | ( expr )
     | NUMBER

对于输入 3 + 4 * 5，这个文法可以生成两种不同的语法树：

  1. 先计算 3 + 4，再乘以 5：(3 + 4) * 5 = 35
  2. 先计算 4 * 5，再加上 3：3 + (4 * 5) = 23

这就是二义性的表现，因为文法没有明确规定运算符的优先级和结合性。

优先级声明

在 Yacc/Bison 中，我们可以使用 %left、%right 和 %nonassoc 指令来声明运算符的优先级和结合性，从而解决二义性问题。

优先级声明的语法：

%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS

优先级规则：

  • 声明的顺序决定优先级，后面的声明优先级更高
  • 例如，上面的声明中，* 和 / 的优先级高于 + 和 -，而 ^ 的优先级更高

结合性声明

结合性决定了相同优先级运算符的求值顺序：

  • %left：左结合，如 a + b + c 解析为 (a + b) + c
  • %right：右结合，如 a ^ b ^ c 解析为 a ^ (b ^ c)
  • %nonassoc：不可结合，如 a < b < c 是不合法的

示例：结合性声明

%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS
%nonassoc '<' '>' '==' '!='

%prec 声明

%prec 声明用于为产生式指定优先级，通常用于处理一元运算符：

expr: '-' expr %prec UMINUS { $$ = -$2; }

这里，一元减号的优先级被指定为与 UMINUS 相同，而 UMINUS 被声明为 %nonassoc，优先级高于其他运算符。

实用案例分析

案例：表达式文法的二义性处理

让我们创建一个处理表达式文法二义性的示例：

Yacc 文件：

/* parser.y */
%{
#include <stdio.h>
#include <math.h>

int yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token EOL

/* 优先级和结合性声明 */
%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS

%%

calc: /* 空规则 */
    | calc expr EOL {
        printf("结果: %g\n", $2);
    }
    | calc EOL
    ;

expr: NUMBER { $$ = $1; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | expr '^' expr { $$ = pow($1, $3); }
    | '-' expr %prec UMINUS { $$ = -$2; }
    | '(' expr ')' { $$ = $2; }
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("带优先级和结合性的计算器\n");
    printf("输入表达式，例如: 3 + 4 * 5, 2 ^ 3 ^ 2, -5 + 3\n");
    return yyparse();
}

Lex 文件：

/* lexer.l */
%{
#include "y.tab.h"
%}

%%

[0-9]+(\.[0-9]+)?  { yylval = atof(yytext); return NUMBER; }
"+"         { return '+'; }
"-"         { return '-'; }
"*"         { return '*'; }
"/"         { return '/'; }
"^"         { return '^'; }
"("         { return '('; }
")"         { return ')'; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

案例：条件表达式的二义性处理

让我们创建一个处理条件表达式二义性的示例：

Yacc 文件：

/* parser.y */
%{
#include <stdio.h>

int yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token IF
%token THEN
%token ELSE
%token EOL

/* 优先级和结合性声明 */
%nonassoc THEN
%nonassoc ELSE

%%

program: /* 空规则 */
       | program stmt EOL
       | program EOL
       ;

stmt: if_stmt
    | expr
    ;

if_stmt: IF expr THEN stmt
       | IF expr THEN stmt ELSE stmt
       ;

expr: NUMBER
    | expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | '(' expr ')'
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("带 else 结合性的解析器\n");
    printf("输入 if-then-else 语句，例如: if 1 then if 2 then 3 else 4\n");
    return yyparse();
}

Lex 文件：

/* lexer.l */
%{
#include "y.tab.h"
%}

%%

[0-9]+      { yylval = atoi(yytext); return NUMBER; }
"if"        { return IF; }
"then"      { return THEN; }
"else"      { return ELSE; }
"+"         { return '+'; }
"-"         { return '-'; }
"*"         { return '*'; }
"/"         { return '/'; }
"("         { return '('; }
")"         { return ')'; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

案例：关系运算符的二义性处理

让我们创建一个处理关系运算符二义性的示例：

Yacc 文件：

/* parser.y */
%{
#include <stdio.h>

int yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token EOL

/* 优先级和结合性声明 */
%nonassoc '<' '>' '<=' '>=' '==' '!='
%left '+' '-'
%left '*' '/'

%%

calc: /* 空规则 */
    | calc expr EOL {
        printf("结果: %d\n", $2);
    }
    | calc EOL
    ;

expr: NUMBER { $$ = $1; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | expr '<' expr { $$ = $1 < $3; }
    | expr '>' expr { $$ = $1 > $3; }
    | expr '<=' expr { $$ = $1 <= $3; }
    | expr '>=' expr { $$ = $1 >= $3; }
    | expr '==' expr { $$ = $1 == $3; }
    | expr '!=' expr { $$ = $1 != $3; }
    | '(' expr ')' { $$ = $2; }
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("带关系运算符的解析器\n");
    printf("输入表达式，例如: 5 > 3, 10 == 5 + 5\n");
    printf("注意: 关系运算符是不可结合的，所以 1 < 2 < 3 是不合法的\n");
    return yyparse();
}

Lex 文件：

/* lexer.l */
%{
#include "y.tab.h"
%}

%%

[0-9]+      { yylval = atoi(yytext); return NUMBER; }
"+"         { return '+'; }
"-"         { return '-'; }
"*"         { return '*'; }
"/"         { return '/'; }
"<"         { return '<'; }
">"         { return '>'; }
"<="        { return '<='; }
">="        { return '>='; }
"=="        { return '=='; }
"!="        { return '!='; }
"("         { return '('; }
")"         { return ')'; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

代码优化建议

  1. 优先级和结合性声明优化：

    • 将相关的运算符分组在同一个声明中，提高代码可读性
    • 按照优先级从低到高的顺序声明，符合常规思维习惯
    • 为所有运算符明确指定优先级和结合性，避免歧义

  2. 错误处理优化：

    • 为不可结合的运算符添加错误处理，提供清晰的错误信息
    • 例如，对于 a &lt; b &lt; c 这样的表达式，给出明确的错误提示

  3. 代码结构优化：

    • 将优先级和结合性声明集中放在文件顶部，便于维护
    • 使用注释说明每个优先级组的含义
    • 为特殊情况（如一元运算符）使用 %prec 明确指定优先级

  4. 性能优化：

    • 合理设置优先级，减少不必要的括号
    • 避免过度复杂的优先级层次，保持简洁

  5. 可维护性优化：

    • 使用命名常量代替字符常量，提高代码可读性
    • 为复杂的表达式文法添加详细的注释
    • 考虑使用 Bison 的 %define 指令自定义解析器行为

总结

本集我们深入学习了二义性文法的处理方法，包括：

  1. 二义性文法的概念和问题
  2. 优先级声明的使用
  3. 结合性声明的使用
  4. %left、%right 和 %nonassoc 指令的含义
  5. %prec 声明的使用
  6. 实际案例：表达式文法、条件表达式和关系运算符的二义性处理
  7. 代码优化建议

通过使用优先级和结合性声明，我们可以有效地解决二义性文法的问题，使语法分析器能够按照预期的方式解析输入。这些技术是构建健壮的语法分析器的重要基础，在后续的编译器开发中会经常用到。

« 上一篇 语法错误处理策略 下一篇 » 二义性文法的处理
↑