语义：描述一个程序的含义

 

上下文无关文法是用来描述语法的一种办法，而描述语义的难度太大。

 

上下文无关文法中的一些概念：

     可以理解为关键字或者一些最小单元的字符，比如while if 0 1 3 之类

     是终结符号的集合，是自己命名的一个东西比如 digit -> 0 | 1|2|3…|8|9，这里digit称为非终结符号

     产生式由两部分组成，左边是非终结符号，右边是非终结符号和终结符号的集合

     比如：digit -> 0 | 1|2|3…|8|9，这一行本身就是产生式

     一段文法的第一行称为开始符号

 

list -> list + digit | list - digit

list -> digit

digit -> 0|1|2|3|4|5|6|7|8|9

 

上面定义了一个文法，然后一个demo：9 - 5 + 3

 

用语法树来解析，过程如下：

 

1.先列出来目标内容

9 - 5 + 3

 

2.然后把他们都看成某个非终结符号

 

digit      digit       digit 

9       -    5     +     3 

 

3.再往上找关系

list

 

可以发现，list - digit可以组成list。

     list

  /         \

 

4.继续

                list

       /                   \

 

这样就根据一个文法定义，一个语句，生成了唯一的语法书，那么这个语句就没有二义性。

你可以试试，先将 5 + 3 -> list + digit，这就变成了list了，然后 9 - list，也就是 digit - list 或者是 list - list ，你就会发现文法中并没有这样的定义，也就是不存在这样的语法，这样也就造成了以上的内容只有一种解析结果。

 

如果从叶子节点开始计算，计算顺序就是 (9 - 5) + 3 是正确的

如果有二义性，那么有可能出现不同的计算顺序，导致结果出错，所以文法的定义没有二义性很重要

 

结合性有左结合和右结合。

 

左结合：

当一个数字左右两边都有运算符的时候，要根据运算符的结合性来决定数字是属于哪一边的

比如+是左结合

1+2+3 -> (1+2)+3 因为2左右两边都有+号，+号是左结合的，所以2是属于左边的运算符。

用文法定义的时候：

result -> result + digit | result

digit -> [0-9]

用语法树来表示

              result

       result       digit

result    digit       |

 digit        |         |

  1      +   2   +   3

 

再看右结合

a = b = c

b的左右两边有运算符 = 

=运算符是右结合的，所以b 是优先属于右边的操作符

a = (b = c)

 

文法定义：

result -> char = result | char

char-> [a-z]

 

用语法树表示：

      result

char     result

|       char  result

|         |       char

a   =   b   =   c 

 

运算符的优先级

比如 * / 和 +- 就是两个级别的运算符，设计文法的时候可以将两个独立的分开比如如下的文法

 

expr -> expr + term | expr - term | term     //expr是加减表达式

term-> term* factor | term/ factor | factor     //term是乘除表达式

factor -> digit | expr

digit -> [0-9]

 

例子

1 + 2 * 3 //我们应该优先计算 2 * 3，直接在本子上画个语法树就出来了，我只能说，真的很巧妙！

 

任意优先级层次的语法

factor理解为一个因子，不可以被任何运算符分开，因为它就是数字本身了

高优先级的运算符可以把低优先级的运算符分开

比如 1 + 2 * 3 

可以看成 1 + x 但是 * 比+的优先级更高，它可以把x分开

 

真心觉得这些东西都非常的巧妙，智慧无穷……

 

原文地址：http://www.cnblogs.com/kross/p/4100317.html

作者：kross(krossford@foxmail.com)