編譯器構造/語法分析

語法分析

這也被稱為解析。它大致相當於檢查用自然語言（例如英語）編寫的普通文字在語法上是否正確（不考慮意義）。

語法分析或解析的目的是檢查我們是否具有有效的令牌序列。令牌是有效的符號、關鍵字、識別符號等的序列。注意，此序列不必有意義；就語法而言，諸如“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();
 }