一個簡單的解析器

編寫解析器的最簡單方法是使用遞迴下降技術。這將建立一個自上而下的解析器（可能正式描述為 LL(1)）。為了開始這個例子，我們首先要為我們的語言建立語法規則。在這個例子中，我們將對只能使用 plus 運算子的表示式使用簡單的算術表示式賦值：

 Assignment --> Identifier := Expression
 Expression --> Expression + Term | Term
 Term --> Identifier | (Expression)
 Identifier --> x | y | z 

對於語法的每個規則，我們可以編寫一個過程來識別規則的傳入令牌。出於本示例的目的，我們可以假設一個名為 NextToken 的例程，它呼叫一個詞法分析器來提供令牌，以及一個名為 error 的例程，它用於輸出錯誤資訊。使用的語言基於 Pascal。

 var token:char;  (* Updated by NextToken *) 

 procedure identifier;
 begin
    if token in ['x','y','z']
    then
        NextToken
    else
        error('Identifier expected')
 end; 

你可以看到此程式碼實現了識別 Identifier 的規則。然後我們可以類似地實現 Term 的規則：

 procedure expression forward; 

 procedure term;
 begin
     if token = '('
     then
         begin
         nextToken;
         expression;
         if token <> ')'
         then
             error(') expected')
         else NextToken
         end
     else
         identifier
 end; 

當我們來實施 Expression 的規則時，我們遇到了問題; Expression 規則的第一個元素本身就是一個 Expression。這將導致我們寫下以下內容：

procedure expression;
begin
expression;
...
end;

這是直接自我遞迴的，因此會永遠迴圈。由於這個原因，由自上而下演算法解析的語法不能是左遞迴的。解決此問題的一個簡單方法是以下列方式將遞迴重新設定為迭代：

Expression --> Term { + Term}* 

我們現在可以將語法規則編碼為：

 procedure expression;
 begin
     term;
     while token = '+'
         do
         begin
             NextTerm;
             term
         end
 end; 

我們現在可以使用剩餘的賦值規則來完成解析器：

procedure assignment;
begin 
    identifier;
    if token <> '='
    then
        error('= expected')
    else
        begin
        NextToken;
        expression;
        end
 end;