一个简单的解析器

编写解析器的最简单方法是使用递归下降技术。这将创建一个自上而下的解析器（可能正式描述为 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;