BNF

BNF 是一种描述程序设计语言的元语言，对语法结构进行抽象。

一个 BNF 语法包含：

  • 终结符 terminals：标记或语素
  • 非终结符 non-terminals
  • 起始符号 start symbol
  • 规则集

语法例子：

1
2
3
4
5
6
<program> → <stmts> 
<stmts> → <stmt> | <stmt> ; <stmts> 
<stmt> → <var> = <expr> 
<var> → a | b | c | d 
<expr> → <term> + <term> | <term> - <term> 
<term> → <var> | const

其中： <program> 是起始符号 ; a, b, c, const,+,-,;,= 是终结符

  • BNF只能描述本地语法，它不能引用程序的另一部分
  • BNF不能进行数值比较

推导

推导：从起始符号开始，每一个后面的字符串都是用非终结符的一个定义来替换前面的字符串中的一个非终结符推出的，知道字符串中都为终结符。

最左推导是指：被替换的非终结符总是前一个句型中最左边的非终结符。

推导可能既不是最左也不是最右。

最左推导的例子

1
2
3
4
5
6
7
8
<program> => <stmts>  
          => <stmt> 
          => <var> = <expr>  
          => a = <expr> 
          => a = <term> + <term>
          => a = <var> + <term>
          => a = b + <term>
          => a = b + const

语法分析树

可能产生歧义 (ambiguous)：如果一个句子形式可以由两个或多个不同的分析树生成，则该语法被认为是歧义的，因为它具有两个或多个不同的含义

例子：考虑语法

1
2
3
4
<exp> → <exp> + <exp> 
      | <exp> * <exp> 
      | (<exp>)  
      | a | b | c

$a+b*c$ 两种不同的生成树

image-20200114144736002

下面是三种消除歧义的语法修改：

优先级 Precedence

运算符优先级“当评估顺序不完全由括号决定时适用”，每个运算符都有一个优先级，并且优先级较高的运算符在优先级较低的优先级之前执行，就像用括号括起来一样

可以通过修改规则得到优先级：

1
<exp> → <exp> + <exp> | <exp> * <exp>  | (<exp>) | a | b | c

修改为：

1
2
<exp> → <exp> + <exp> | <mulexp> 
<mulexp> → <mulexp> * <mulexp> | (<exp>)| a | b | c

使得乘法拥有更高的优先级，对于 $a+b*c$ 只有一种生成树：

image-20200114150407116

结合性 Associativity

当评估顺序不是由括号或优先级决定时适用

  • 左结合 (Left-associative) 运算符将操作数从左到右分组：

    $a + b + c + d =((a + b)+ c)+ d$

  • 右结合 (Right-associative) 运算符将操作数从右到左分组：

    $a + b + c + d = a +(b +(c + d))$

在上面的语法中 $a+b+c$ 会产生两种生成树

image-20200114150806038

左边生成树中 + 为右结合运算符；右边生成树中 + 为左结合运算符；

可以通过修改规则得到指定的结合性：

1
2
<exp> → <exp> + <exp> | <mulexp> 
<mulexp> → <mulexp> * <mulexp> | (<exp>)| a | b | c

修改为：

1
2
3
<exp> → <exp> + <mulexp> | <mulexp>
<mulexp> → <mulexp> * <rootexp> | <rootexp>
<rootexp> → (<exp>)| a | b | c

这是一个左结合的语法。

image-20200114152022613

if-then-else

假设有语法：

1
2
3
4
<stmt> → <if-stmt> | s1 | s2
<if-stmt> → if <expr> then <stmt> else <stmt>
           | if <expr> then <stmt>
<expr> → e1 | e2

会带来歧义：考虑 if e1 then if e2 then s1 else s2, 两种生成树

image-20200114152423993

修改语法为：

1
2
3
4
5
6
<full-stmt> → <full-if> | s1 | s2
<full-if> → if <expr> then <full-stmt> else <full-stmt>
<stmt> → <if-stmt> | s1 | s2
<if-stmt> → if <expr> then <full-stmt> else <stmt>
           | if <expr> then <stmt>
<expr> → e1 | e2

语法的思路是：如果有 else 语句，它与前面最近一个没有匹配的 then 相匹配，因此在 then 和匹配的 else 中间不可能有一个没有 else 的 if 语句。使用新的非终结符表示若有 if 一定有 else 的 语句。

在这种实现下，只能生成第二种语法树。

EBNF

EBNF (Extended BNF) 是BNF的一些简单扩展，使语法表达更加方便。

它比BNF更为简洁，但 EBNF并不比BNF更“强大”：只是添加 “syntactic sugar”。也就是说，用EBNF表示的任何内容也可以用BNF表示。

EBNF被广泛用作定义编程语言的事实标准。

常见语法

  1. [] 表示可选部分

    1
    2
    3
    4
    5
    BNF:
    <if-stmt> → if <expr> then <stmt> else <stmt>
               | if <expr> then <stmt>
    EBNF:
    <if-stmt> → if <expr> then <stmt> [else <stmt>]

  2. {} 表示括起来部分可以重复无数次或整体省去

  3. 可以用 () 表示在其中选择其中一个元素

    1
    2
    3
    4
    5
    6
    BNF   
    <expr> → <expr> + <term> | <expr> - <term> | <term>
    <term> → <term> * <factor>  | <term>/<factor> | <factor> 
    EBNF   
    <expr> → <term> {(+ | -) <term>} 
    <term> → <factor> { (* | /) <factor>}
其他语法
1
2
3
4
5
BNF:
<expr> → <digits> 
<digits>  → <digit> | <digit> <digits> 
EBNF:
<expr> ::= <digit>+ 
1
2
3
4
5
BNF:
<expr> → <digits> |  empty
<digits>  → <digit> | <digit> <digits> 
EBNF:
<expr> ::= <digit>*
1
2
3
4
BNF:
<id> →  <letter> | <id><letter> | <id><digit> 
EBNF:
<id> → <letter> (<letter> |  <digit>)*

似曾相识emmm

EBNF 表示 Lisp 语法
1
2
3
4
5
6
7
8
9
10
s_expression → atomic_symbol 
    | "(" s_expression "." s_expression ")" 
    | list 
list → "(" s_expression* ")" 
atomic_symbol → letter atom_part 
atom_part → empty 
    | letter atom_part 
    | number atom_part 
letter → "a" | "b" | " ..." | "z" 
number → "1" | "2" | " ..." | "9"

BNF & EBNF

BNF to EBNF
1
2
3
A → a A | B
⇒
A → {a} B
1
2
3
A → a B | a
⇒
A → a [B]
EBNF to BNF
1
2
3
4
A → a [B] C
⇒
A → a N C
N → B | empty
1
2
3
4
A → a {B1 B2 ... Bn} C
⇒
A → a N C
N → B1 B2 ... Bn N | empty