编译器构造/语法分析

语法分析

这也被称为解析。它大致相当于检查用自然语言（例如英语）编写的普通文本在语法上是否正确（不考虑意义）。

语法分析或解析的目的是检查我们是否具有有效的令牌序列。令牌是有效的符号、关键字、标识符等的序列。注意，此序列不必有意义；就语法而言，诸如“true + 3”之类的短语在大多数编程语言中是有效的，但没有意义。

解析器获取在词法分析阶段生成的令牌，并尝试构建某种内存内结构来表示该输入。通常，该结构是“抽象语法树”（AST）。

解析器需要能够处理可能呈现给它的无限数量的可能的有效程序。定义语言的通常方法是指定一个语法。语法是规则（或产生式）的集合，它指定语言的语法（即语言中什么是有效的句子）。

对于给定的语言，可以有多个语法。此外，为某些语法构建解析器比为其他语法更容易。

幸运的是，存在一类程序（通常称为“编译器编译器”，尽管这是一个愚蠢的名称），它可以接受语法并为其生成某种语言的解析器。（听起来熟悉？）。此类程序的示例包括

ANTLR（针对 Java、C++ 和 C#）
SableCC（针对 Java）
YACC（针对 C）
YACC++（针对 C++）
以及许多其他...

如果他们可以写下他们语言的语法，这些可以使编译器编写者的工作变得容易得多。

递归下降分析

递归下降解析器是一个自顶向下的解析器，它由一组相互递归的程序（或非递归等效程序）构建，其中每个程序通常实现语法中的一个产生式规则。因此，生成的程序的结构与它识别的语法的结构密切相关。

预测解析器是一种没有备份的递归下降解析器。预测解析仅适用于 LL(k) 语法的类别，这些语法是存在某个正整数 k 的上下文无关语法，该整数允许递归下降解析器通过仅检查输入的下一个 k 个令牌来决定使用哪个产生式。（因此，LL(k) 语法排除了所有歧义语法，以及所有包含左递归的语法。任何上下文无关语法都可以转换为等效的没有左递归的语法，但删除左递归并不总是产生 LL(k) 语法。）预测解析器在线性时间内运行。

带有备份的递归下降是一种通过依次尝试每个产生式来决定使用哪个产生式的技术。带有备份的递归下降不限于 LL(k) 语法，但除非语法是 LL(k)，否则它不能保证终止。即使它们终止，使用带有备份的递归下降的解析器也可能需要指数时间。

虽然预测解析器被广泛使用，但程序员通常更愿意通过解析器生成器创建 LR 或 LALR 解析器，而不会将语法转换为 LL(k) 形式。

一些作者将递归下降解析器定义为预测解析器。其他作者更广泛地使用这个术语，包括备份的递归下降。[需要引用]

示例解析器

以下 EBNF 语法（针对尼克劳斯·维尔特的 PL/0 编程语言，来自算法 + 数据结构 = 程序）采用 LL(1) 形式（为简单起见，假设 ident 和 number 是终结符）

program = block "." .

block =
    ["const" ident "=" number {"," ident "=" number} ";"]
    ["var" ident {"," ident} ";"]
    {"procedure" ident ";" block ";"} statement .

statement =
    [ident ":=" expression
    | "call" ident
    | "begin" statement {";" statement} "end"
    | "if" condition "then" statement
    | "while" condition "do" statement
    ] .

condition =
    "odd" expression
    | expression ("="|"#"|"<"|"<="|">"|">=") expression
    .

expression = ["+"|"-"] term {("+"|"-") term} .

term = factor {("*"|"/") factor} .

factor = ident | number | "(" expression ")" .

终结符用引号表示（除了 ident 和 number）。每个非终结符由语法中的规则定义。

请注意下面的预测解析器是如何与上面的语法紧密对应的。语法中每个非终结符都有一个过程。解析以自顶向下的方式下降，直到处理完最后一个非终结符。程序片段取决于一个全局变量 sym，它包含来自输入的下一个符号，以及全局函数 getsym，它在被调用时更新 sym。

typedef enum {ident, number, lparen, rparen, times, slash, plus,
   minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
   endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
   varsym, procsym, period, oddsym} Symbol;

Symbol sym;
void getsym(void);
void error(const char msg[]);
void expression(void);

int accept(Symbol s) {
   if (sym == s) {
       getsym();
       return 1;
   }
   return 0;
}

int expect(Symbol s) {
   if (accept(s))
       return 1;
   error("expect: unexpected symbol");
   return 0;
}

void factor(void) {
   if (accept(ident)) {
       ;
   } else if (accept(number)) {
       ;
   } else if (accept(lparen)) {
       expression();
       expect(rparen);
   } else {
       error("factor: syntax error");
       getsym();
   }
}

void term(void) {
   factor();
   while (sym == times || sym == slash) {
       getsym();
       factor();
   }
}

void expression(void) {
   if (sym == plus || sym == minus)
       getsym();
   term();
   while (sym == plus || sym == minus) {
       getsym();
       term();
   }
}

void condition(void) {
   if (accept(oddsym)) {
       expression();
   } else {
       expression();
       if (sym == eql || sym == neq || sym == lss ||
           sym == leq || sym == gtr || sym == geq) {
           getsym();
           expression();
       } else {
           error("condition: invalid operator");
           getsym();
       }
   }
}

void statement(void) {
   if (accept(ident)) {
       expect(becomes);
       expression();
   } else if (accept(callsym)) {
       expect(ident);
   } else if (accept(beginsym)) {
       do {
           statement();
       } while (accept(semicolon));
       expect(endsym);
   } else if (accept(ifsym)) {
       condition();
       expect(thensym);
       statement();
   } else if (accept(whilesym)) {
       condition();
       expect(dosym);
       statement();
   }
}

void block(void) {
   if (accept(constsym)) {
       do {
           expect(ident);
           expect(eql);
           expect(number);
       } while (accept(comma));
       expect(semicolon);
   }
   if (accept(varsym)) {
       do {
           expect(ident);
       } while (accept(comma));
       expect(semicolon);
   }
   while (accept(procsym)) {
       expect(ident);
       expect(semicolon);
       block();
       expect(semicolon);
   }
   statement();
}

void program(void) {
   getsym();
   block();
   expect(period);
}

函数式语言中的实现

递归下降解析器在 Haskell 或 ML 等函数式语言中特别容易实现。

参见函数式珍珠：Haskell 中的单子解析

另请参见

JavaCC - 一个递归下降解析器生成器
Coco/R - 一个递归下降解析器生成器
ANTLR - 一个递归下降解析器生成器
CodeCodex：递归下降解析 - C、Java 和 OCaml 的示例递归下降解析器生成器代码
尾递归解析器 - 递归下降解析器的一种变体

表驱动分析

运算符优先级分析

运算符优先级分析用于移进-归约分析。运算符语法 没有任何产生式的右边具有两个非终结符相继出现。可以使用移进-归约分析和终结符之间的优先级关系来解析运算符语法，以找到句柄。这种策略被称为运算符优先级。

通过工具解析 - yacc/bison

维基百科 GNU bison 文章。

通过工具解析 - JavaCC

请参阅词法分析：通过工具扫描 - JavaCC，以获取有关生成令牌管理器的信息。

使用生成的 Token 管理器

为了使用生成的令牌管理器，必须创建它的实例。这样做时，构造函数期望一个 Reader 作为输入数据的来源（其他来源也是可能的，请参阅 JavaCC 文档）。

创建后，令牌管理器对象可用于通过以下方式获取令牌

Token ParserNameTokenManager.getNextToken() throws ParseError;

方法。

每个 Token 对象都由 getNextToken() 方法返回。这样的 Token 对象提供一个kind 字段，用于标识令牌（ParserNameConstants.java 定义了相应的常量）。它还包含image 字段，它仅将匹配的输入数据作为一个字符串保存。

语法分析器的示例是

 #include<stdio.h>
 #include<conio.h>
 #include<string.h>
 #include<ctype.h>
 //
 void main() {
   int i,j,k=0,count,inc=0,n;
   char name[30],open[30],ch,chh,o[30];
   char op[20]={'=','+','-','*','/','%','^','&','|'};
   clrscr();
   textcolor(3);
   cprintf("--Syntax Analyser--");
   printf("\n");
   printf("\n Enter Syntax");
   printf("\n");
   scanf("%s",name);
   n=strlen(name);
   for(i=0;i<n;i++) {
     ch=tolower(name[i]);
     for(j=0;j<9;j++) {
       if(ch==op[j]) {
         open[k]=i;
         o[k]=ch;
         k++;
       }
     }
   }
   for(i=0;i<k;i++) {
     count=open[i];
     ch=tolower(name[count-1]);
     chh=tolower(name[count+1]);
     if(isalpha(ch)&&isalpha(chh)||isdigit(chh))
       ++inc;
   }
   if(k==inc)
     printf("\n %s is a valid syntax",name);
   else
     printf("\n %s is an invalid syntax",name);
   getch();
 }