表达式的文法设计

Author Avatar
zccz14 6月 04, 2017
  • 在其它设备中阅读本文章

比起汇编,高级语言支持更加复杂的表达式。表达式主要是由操作数(Operands)与操作符(Operators)组成。

而且就事实而言,不论其原因,大多数人习惯使用中缀表达式,这是一种将操作符放在操作数之间的表示法。

而就是因为这种表示法有着计算顺序上的局限性,有时候我们需要使用括号来确定计算的优先级。

操作符有几个重要的特性:元数、优先级、结合性、语义动作。

接下来使用 BNF 范式说明表达式文法的设计方法。

引例:四则运算文法

以一个简单的四则运算文法开始(BNF描述):

1
2
3
4
<Expression> ::= <Expr1>
<Expr1> ::= <Expr1> <OP Add> <Expr2> | <Expr1> <OP Sub> <Expr2> | <Expr2>
<Expr2> ::= <Expr2> <OP Mul> <Expr3> | <Expr2> <OP Div> <Expr3> | <Expr3>
<Expr3> ::= <Number> | <Identifier> | <Delimiter LeftParenthese> <Expression> <Delimiter RightParenthese>

其中,<OP Add> 是指加号这个运算符<Delimiter LeftParenthese> 是指左括号这个界符,其他不一一说明了。

给定一个符号(Token)串,可以进行文法推导,

例如 2 * a + (1 - a) / a 需要先通过词法分析得到符号串:

1
2
3
4
5
6
7
8
9
10
11
<Number 2>
<OP Mul>
<Identifier a>
<OP Add>
<Delimiter LeftParenthese>
<Number 1>
<OP Sub>
<Identifier a>
<Delimiter RightParenthese>
<OP Div>
<Identifier a>

然后我们的目标是从 <Expression> 作为文法的起始符号开始推导(以一种XML语法树记法):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
<Expression>
<Expr1>
<Expr2>
<Expr2>
<Expr3>
<Number value="2"/>
</Expr3>
</Expr2>
<OP type="Mul"/>
<Expr3>
<Identifier name="a"/>
</Expr3>
</Expr2>
</Expr1>
<OP type="Add"/>
<Expr2>
<Expr2>
<Expr3>
<Delimiter type="LeftParenthese"/>
<Expression>
<Expr1>
<Expr1>
<Expr2>
<Expr3>
<Number value="1"/>
</Expr3>
</Expr2>
</Expr1>
<OP type="Sub"/>
<Expr2>
<Expr3>
<Identifier name="a"/>
</Expr3>
</Expr2>
</Expr1>
</Expression>
<Delimiter type="RightParenthese"/>
</Expr3>
</Expr2>
<OP type="Div"/>
<Expr3>
<Identifier name="a"/>
</Expr3>
</Expr2>
</Expression>

文法设计方法

表达式的文法设计的重点在于根据算符的特性进行设计。

主要就是元数、优先级、结合性。

形式化地讨论:

  • 如果一个二元运算符 <OP X> 的优先级是 N ,左结合,那么其在文法中体现为:

    1
    <Expr{N}> ::= <Expr{N}> <OP X> <Expr{N+1}>
  • 如果一个二元运算符 <OP X> 的优先级是 N ,右结合,那么其在文法中体现为:

    1
    <Expr{N}> ::= <Expr{N+1}> <OP X> <Expr{N}>
  • 如果一个一元运算符 <OP X> 的优先级是 N ,左结合,那么其在文法中体现为:

    1
    <Expr{N}> ::= <Expr{N}> <OP X>
  • 如果一个一元运算符 <OP X> 的优先级是 N ,右结合,那么其在文法中体现为:

    1
    <Expr{N}> ::= <OP X> <Expr{N}>

更一般地,一个K元运算符(K > 1),其中缀记法必然有 K - 1 个符号,假设其互不相同,记为 <OP X1>, <OP X2>, ..., <OP X{K-1}>,优先级是 N

当其为左结合时:

1
<Expr{N}> ::= <Expr{N}> <OP X1> <Expr{N+1}> <OP X2> ... <Expr{N+1}> <OP X{K-1}> <Expr{N+1}>

当其为右结合时:

1
<Expr{N}> ::= <Expr{N+1}> <OP X1> <Expr{N+1}> <OP X2> ... <Expr{N+1}> <OP X{K-1}> <Expr{N}>

消除左递归

只有左结合的文法产生式会有左递归的问题,在自上而下的语法分析中可能会GG,所以可以改写一下:

对于一元运算符 <OP X>

1
2
<Expr{N}> ::= <Expr{N+1}> <ExprR{N}>
<ExprR{N}> ::= <OP X> <ExprR{N}> | <Epsilon>

一个K元运算符(K > 1) <OP X1>, <OP X2>, ..., <OP X{K-1}>

1
2
<Expr{N}> ::= <Expr{N+1}> <ExprR{N}>
<ExprR{N}> ::= <OP X1> <Expr{N+1}> <OP X2> ... <Expr{N+1}> <OP X{K-1}> <Expr{N+1}> <ExprR{N}> | <Epsilon>

这种改写法其实是用了一种剩余(Remain)的思想去描述的。