文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

Language

发布于 2025-01-31 22:20:47 字数 25672 浏览 0 评论 0 收藏 0

天地玄黄、宇宙洪荒、日月盈昃、辰宿列张。《千字文》

Language / Grammar

Language 是一大堆字串。Language 是一个字串集合。

括号对称的 Language
使用的字元是“(”与“)”。

()
()()()
(((())))
(((()(()))()))
......

圣经人名的 Language
使用的字元是 52 种大小写英文字母。

Aaron
Abaddon
Abagtha
Abana
Abba
Abda
......

C Programming Language
使用的字元是 ASCII 当中的可见符号、换行、空白等等。

int main() {return 0;}

int main(int argc, char* argv[]) {return 0;}

int main( int argc , char * argv[] ) {
    return 0;
}

English Language
使用的字元是 52 种大小写英文字母、标点符号。

Whatever, you know, just sayin.
How are you? I am fine, thank you.

Chinese Language
使用的字元是汉字，大约七万字。

臣亮言：先帝创业未半，而中道崩殂；今天下三分，益州疲敝，此诚危急存亡之秋也。
为著环境未冻来完成彼段永远难忘的恋情。孤单来到昔日的海岸，景致犹原也无改变。
为了防止世界被破坏，为了守护世界的和平，贯彻爱与真实的邪恶。

Grammar 是一组规则，用三言两语构筑一大堆字串、构筑一套 Language。一套 Language 可以设计许多种不同的 Grammar，不过光是学一种 Grammar 就够头痛了。

Grammar 理论上必须刚好生成 Language 之内的所有字串、永不生成 Language 以外的所有字串。

English Grammar
主词 S，动词 V，受词 O，补语 C。

1. S + V
2. S + V + C
3. S + V + O
4. S + V + O + C
5. S + V + O + O
6. V + S + O
7. S + do/does + V + C
......
......
......
123. S = dog / cat / ...
124. V = run / sleep / ...
......
......
......

以数学的角度来看，Grammar 就像是数学公式。从资料结构的角度来看，Grammar 是 Language 的资料结构。从资料压缩的角度来看，不失真地压缩 Language，就得到 Grammar。

Syntax / Semantics

“语法 Syntax”是字串的格式；字串对应到文法即可求得。

      I            love          you.
[名词主格 nom.] [及物动词 vt.] [名词受格 obj.]

  我     爱     你。
[名词] [动词] [受词]

“语意 Semantics”是字串的含意；确立语法之后，根据上下文、根据现场情境求得。

小孩对妈妈说：我　爱　你。
　　　　　　　[温馨的亲情]

丈夫对妻子说：我　爱　你。
　　　　　　　[甜蜜的爱情]

丈夫强忍眼泪，紧抱著患病的妻子说：我　爱　你。
　　　　　　　　　　　　　　　　　[心痛的悲情]

Parse / Evaluate

剖析解读语法，求值总结语意。

我们可以“剖析 Parse”一个字串，逐字对应至 Grammar、确立语法，进而判断原本字串是不是 Language 当中的字串。

字串对应到文法时，有两种以上的对应方式，那麽此文法就称作“暧昧文法 Ambiguous Grammar”。

暧昧文法使得同一个字串拥有许多种语法，难以剖析。暧昧文法也很容易让人误解字串涵义，而中文文法就是一个著名的暧昧文法。例如下面两例，每一行句子的语法都略有不同。

已结婚的和尚未结婚的青年都要实行生育计画

一、已结婚的、和、尚未结婚的青年，都要实行生育计画！（“和”当作连词）
二、已结婚的和尚、未结婚的青年，都要实行生育计画！（“和尚”当作名词）

下雨天留客天留我不留

一、下雨，天留客。天留，我不留。
二、下雨，天留客。天留我？不留。
三、下雨，天留客。天留我不？留。
四、下雨，天留客。天，留我不留？
五、下雨天，留客天。留我？不留。
六、下雨天，留客天。留我不？留。
七、下雨天，留客天。留我不留？

接著可以“求值 Evaluate”一个字串，逐字确认语意，进而得到原本字串的意义。

例如下例第一句是语法和语意都正确；第二句是语法正确、语意採用了转化修辞；第三句是语法正确、语意不正确，语焉不详。

女孩对我眨眼。
星星对我眨眼。
空气对我眨眼。

例如下例第一句、第三句之中重複的地方，就是语法相同、语意不同。第二句是语法不同、语意也不同。

有两种人不谈恋爱：一种是谁都看不上，另一种是谁都看不上。
有两种人最容易被甩：一种人不知道什麽叫做爱，一种人不知道什麽叫做爱。
这些人都是原先喜欢一个人，后来喜欢一个人。

电脑习惯先判定语法、再判定语意，暧昧文法应予尽量避免。人类习惯先揣摩语意、再揣摩语法，暧昧文法实则影响不大。

UVa 271 310 384 620 743 1089 10027 10981 11108 ICPC 3623 4455

Formal Language / Natural Language

接下来要介绍的 Language，是以数学方式建构而得的语言，是一套数学理论，称作“制式语言 Formal Language”。

人类互相交流的语言，例如中文、英文、闽南语、客家话、粤语，则相对地称作“自然语言 Natural Language”。

以数学方式建构而得的语言，规律太过完美，不足以表达现实生活那些缺乏规律的语言。解析人类语言的方法，是自成一系的古老学问，属于“语言学 Linguistics”的范畴，是人文方面的学问。

运用电脑处理人类语言，例如语言翻译、人机对话等等，则是属于“计算语言学 Computational Linguistics”的范畴。

Formal Language 四大类型

Regular Language
Context-free Language
Context-sensitive Language
Unrestricted Language

古早人以数学方式，研发了四种语言规律，由规律严谨到规律宽鬆排列，前者是后者的特例。

其中 Regular Language 与 Context-free Language，由于规律十分严谨，所以得以设计效率极高的演算法、拥有实务价值。

例如 Regular Language 用于字串匹配、用于验证字串格式。例如 Context-free Language 用于设计程式语言、用于检索网页资料。身为一个程式员，其实每天都在不自觉地接触这些语言的应用。

至于 Context-sensitive Language 与 Unrestricted Language，由于缺乏规律、难以计算，所以鲜少讨论。

Regular Language

“正规语言”规律十分简单：

一、空集合：一套正规语言可以只包含一个字串，而且是空字串。
{Ø}

二、字元：一套正规语言可以只包含一个字串，而且是长度为一的字串。
{a}、{b}、{c}

三、衔接：一套正规语言可以只包含一个字串，是上述某些字串衔接而得的字串。
{aa}、{aaa}、{aaabbb}、{abc}、{aabbccabc}、{ababab}

四、联集：一套正规语言可以是上述某些字串的联集。
{aaabbb, ab, ba, cat, dog, Ø}
{Aaron, Abaddon, Abagtha, Abana, Abba, Abda, ......}

Regular Expression

一个“正规表示式”就是一种文法，轻鬆描述一套正规语言。书写语法如下表所示：

   | RegExp | Regular Language        | 意义
---| -------| ------------------------| ---------------
   | ab     | {ab}                    | 衔接
   | abc    | {abc}                   |
---| -------| ------------------------| ---------------
() | (ab)   | {ab}                    | 包装
   | (ab)c  | {abc}                   |
---| -------| ------------------------| ---------------
+  | a+     | {a, aa, aaa, ...}       | 出现一次以上
   | ab+    | {ab, abb, abbb, ...}    |
   | (ab)+  | {ab, abab, ababab, ...} |
   | a+b    | {ab, aab, aaab, ...}    |
---| -------| ------------------------| ---------------
*  | a*     | {Ø, a, aa, aaa, ...}    | 出现零次以上
   | ab*    | {a, ab, abb, abbb, ...} |
---| -------| ------------------------| ---------------
?  | a?     | {Ø, a}                  | 出现零次或一次
   | abc?   | {ab, abc}               |
   | (abc)? | {Ø, abc}                |
   | a?b    | {b, ab}                 |
---| -------| ------------------------| ---------------
{} | a{3,5} | {aaa, aaaa, aaaaa}      | 出现 x 次或至 y 次
---| -------| ------------------------| ---------------
|  | a|b    | {a, b}                  | 联集
   | a|b|c  | {a, b, c}               |
   | ab|cd  | {ab, cd}                |
   | (a|b)c | {ac, bc}                |
   | (a|b)? | {Ø, a, b}               |
   | (a|b)+ | {a, b,                  |
   |        |  aa, ab, ba, bb,        |
   |        |  aaa, aab, aba, ...}    |
---| -------| ------------------------| ---------------
[] | [abc]  | {a, b, c}               | 字元的联集
   | [a-z]  | {a, b, c, ..., z}       |
   | [a-zA] | {a, ..., z, A}          |
   [a-zA-Z] | {a, ..., z, A, ..., Z}  |
---| -------| ------------------------| ---------------
.  | .      | {a, b, c, ...,          | 全部字元的联集
   |        |  A, B, C, ...,          | 或者说
   |        |  1, 2, 3, ...,          | 任意一个字元
   |        |  (, ), +, *, ?, ... }   |
   | a.     | {aa, ab, ac, ...}       |
   | a..    | {aaa, aab, aac, ...}    |
---| -------| ------------------------| ---------------
\  | \(     | {(}                     | escape
   | \.     | {.}                     |

注：作业系统的档案名称，也常常写成正规表示式，例如*.txt。但是档案名称採用的是另一种书写语法，像是?是指任意一个字元、*是指任意一个字串，都与上表的意义不同。千万不要搞混。

范例：行动电话号码

台湾的行动电话号码，诸如 0935-120-188、0982647356 等等，所有的行动电话号码字串构成的集合，正是一套正规语言。对应的正规表示式有许多种写法：

09[0-9][0-9]-?[0-9][0-9][0-9]-?[0-9][0-9][0-9]
09[0-9]{2,2}-?[0-9]{3,3}-?[0-9]{3,3}
09[0-9]{2,2}(-?[0-9]{3,3}){2,2}
09([0-9][0-9]-?[0-9]){2,2}[0-9][0-9]
......

先前提到一套语言可以设计许多种不同的文法，想当然一套正规语言可以设计许多种正规表示式。

范例：浮点数

程式语言的浮点数，诸如-1.23、4.56e-7 等等，所有的浮点数字串构成的集合，正是一套正规语言。对应的正规表示式为：

[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?

UVa 325

String Verification / Wildcard String Matching

大部分的程式语言都有内建正规表示式的功能，可以验证一个字串是否符合给定的正规表示式（字串验证），还可以搜寻一个字串、找到符合正规表示式的字串片段（万用字元字串匹配）。

万用字元字串匹配当中，当出现多种匹配位置，默认的结果是匹配位置尽量靠左、然后匹配长度尽量长。另外也有特殊语法可以限制匹配位置：

   | String | RegExp | Matching | 意义
---| -------| -------| ---------| --------------------
^  | abcabc | ^ab    | ab       | 一定要出现于字串开头
   | abcabc | ^a.*   | abcabc   |
---| -------| -------| ---------| --------------------
$  | abcabc | ab$    | Ø        | 一定要出现于字串结尾
   | abcabc | ^a.*c$ | abcabc   |

字串验证、万用字元字串匹配，有著许多实际运用：

例如用正规表示式一口气涵盖所有需要的档案名称。

例如申请网站帐号、例如网路购物，表单必须输入帐号名称、生日、电话、地址等。可以用正规表示式，验证使用者输入的格式是否正确： http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/ 。

例如公司欲侦测员工是否偷玩脸书、偷逛网拍，就在防火牆安装 snort，设计正规表示式，撷取送往脸书与购物网站的封包。

演算法（Backtracking）

此处实作的是常见的 grep 指令。一开始的时候、以及遇到*号的时候，就穷举各种匹配位置，递迴下去判断是否匹配；其他符号则循序匹配。

时间複杂度与正规表示式之中*号的数量有关。无星号，就是普通的字串匹配，时间複杂度为 O(TR)，其中 T 为字串长度、R 是正规表示式长度；有星号，我就不会分析了，或许跟 k-partition problem 差不多。

UVa 10058

演算法（Thompson's Algorithm）

http://swtch.com/~rsc/regexp/regexp1.html

http://swtch.com/~rsc/regexp/

正规表示式等价地转换成 Non-deterministic Finite Automata, NFA。字串匹配的空间複杂度为 O(R)，时间複杂度为 O(TR)。

可以再等价地转换成 Deterministic Finite Automata, DFA。字串匹配的空间複杂度上升为 O(2^R)、时间複杂度降低为 O(T)。

UVa 12415 891 1671 1672 ICPC 6670

Regular Language 的能力极限

正规语言是循序性的语言，不具备从属关係、阶层关係、巢状结构、树状结构、递迴结构。

如果你没勇气陪我到明天的明天的明天倒不如就忘了就断了寂寞的昨天的昨天

　明天　　　　　　昨天
　｜　　　　　　　｜
　明天（后天）　　昨天（前天）
　｜
　明天（大后天）

【感情应该要慢慢培养。这前前后后也才六天，用不著这麽激动吧。】

有一个发人省思的故事是：“哥哥说：‘爸爸跟我说过：“说话要诚实，不可以
欺骗别人。”但是妈妈也跟我说过：“说话太诚实，常常无意间伤害别人。”’
弟弟说：‘老师有说：“子曰：‘巧言令色，鲜矣仁。’”，爸爸是对的！’”
这个故事告诉我们：正规语言难以釐清到底谁说了哪句话。

　全文＿＿＿＿＿＿＿＿＿＿＿＿
　｜　　　　　　　　　　　　　｜
　故事说＿＿＿＿＿＿　　　　　我想说
　｜　　　　　　　　｜　　　　｜
　哥哥说＿　　　　　弟弟说　　正规语言
　｜　　　｜　　　　｜
　爸爸说　妈妈说　　老师说
　｜　　　｜　　　　｜
　要诚实　别太诚实　孔子说
　　　　　　　　　　｜
　　　　　　　　　　巧言令色

永和有永和路，中和有中和路，
中和的中和路有接永和的中和路，永和的永和路没接中和的永和路；
永和的中和路有接永和的永和路，中和的永和路没接中和的中和路。
永和有中正路，中和有中正路，永和的中正路用景平路接中和的中正路；
永和有中山路，中和有中山路，永和的中山路直接接上了中和的中山路。
永和的中正路接上了永和的中山路，中和的中正路却不接中和的中山路。
中正桥下来不是中正路，但永和有中正路；
秀朗桥下来也不是秀朗路，但永和也有秀朗路。
永福桥下来不是永福路，永和没有永福路；
福和桥下来不是福和路，但福和路接的是永福桥。

【这个乱到我实在画不出阶层架构图，诚徵在地人帮忙画个纯文字版的架构图。】

教科书经常用下例说明正规语言的能力极限：

连续的“(”紧接著连续的“)”，并且“(”与“)”刚好一样多的语言。

按照数学定义，正规文法只能是有限长度，但是正规语言可以是有限集合或无限集合。我们可以使用穷举法、预处理的思路，联集所有层次的括号，涵盖这个语言；但是当括号层数不固定、可达无限多层时，就无法用有限长度的正规表示式涵盖这个语言了。

Regular Expression         | Regular Language
---------------------------| ---------------------------
                           | {Ø}
\(\)                       | {Ø, ()}
\(\)|\(\(\)\)              | {Ø, (), (())}
\(\)|\(\(\)\)|\(\(\(\)\)\) | {Ø, (), (()), ((()))}
---------------------------| ---------------------------
not exist                  | {Ø, (), (()), ((())), ...}
                           | it's not a regular language
---------------------------| ---------------------------
\(*\)*                     | {Ø, (, ), ((, (), )), ...}
(\(\))*                    | {Ø, (), ()(), ()()(), ...}

更进一步来说，拥有巢状括号、括号裡面又有文字的语言，也不是正规语言。实务上我们可以运用大量正规表示式，逐次得到每一层每一个括号裡面的字串，然后建立阶层架构；但是当巢状括号没有固定的数量，实在是不适合採用这种方式。

诸如四则运算式子、HTML、C 程式语言等等，都不是正规语言，而是接下来介绍的 Context-free Language。

Context-free Language

Context-free Grammar

一个上下文无关文法，有许多条衍生规则。规则裡面是符号、字元、箭头。

个位数四则运算文法：
S -> SAS
S -> (S)
S -> 0
S -> 1
...
S -> 9
A -> +
A -> -
A -> ×
A -> ÷

从起始符号 S 开始，随意套用规则、不断衍生，直到消除所有符号、形成一个字串。

套用各种规则，所得到的各种字串，就是该文法对应的语言。

rule     | string     rule     | string     rule     | string 
---------| -------    ---------| -------    ---------| -------
         | S                   | S                   | S      
S -> SAS | SAS        S -> 0   | 0          S -> SAS | SAS    
A -> ×   | S×S                              S -> SAS | SASAS  
S -> (S) | (S)×S      rule     | string     S -> 1   | SA1AS  
S -> 1   | (S)×1      ---------| -------    A -> -   | SA1-S  
S -> SAS | (SAS)×1             | S          S -> 7   | 7A1-S  
S -> 3   | (3AS)×1    S -> (S) | (S)        A -> ÷   | 7÷1-S  
S -> 2   | (3A2)×1    S -> 0   | (0)        S -> 3   | 7÷1-3  
A -> +   | (3+2)×1

language = {(3+2)×1, 0, (0), 7÷1-3, ...}

一律先消除最左边的符号，称作“左衍生 leftmost derivation”；一律先消除最右边的符号，称作“右衍生 rightmost derivation”。调整消除符号的顺序，不会改变字串，可以放心调整。

採用左衍生或者右衍生，可以让别人容易看懂衍生过程，是比较贴心的方式。

                      leftmost derivation   rightmost derivation
rule     | string     rule     | string     rule     | string 
---------| -------    ---------| -------    ---------| --------
         | S                   | S                   | S      
S -> SAS | SAS        S -> SAS | SAS        S -> SAS | SAS    
A -> ×   | S×S        S -> (S) | (S)AS      S -> 1   | SA1    
S -> (S) | (S)×S      S -> SAS | (SAS)AS    A -> ×   | S×1    
S -> 1   | (S)×1      S -> 3   | (3AS)AS    S -> (S) | (S)×1  
S -> SAS | (SAS)×1    A -> +   | (3+S)AS    S -> SAS | (SAS)×1
S -> 3   | (3AS)×1    S -> 2   | (3+2)AS    S -> 2   | (SA2)×1
S -> 2   | (3A2)×1    A -> ×   | (3+2)×S    A -> +   | (S+2)×1
A -> +   | (3+2)×1    S -> 1   | (3+2)×1    S -> 3   | (3+2)×1

“上下文无关”是指符号不会连带上下文一起衍生。也就是每条规则的左式，只有一个符号，而不会连带其他符号和字元。

A   -> By    context-free
A   -> xBy   context-free
A   -> xByCz context-free
A   -> xyz   context-free
xAy -> B     context-sensitive
xA  -> B     context-sensitive
xA  -> yB    context-sensitive
AB  -> C     context-sensitive

正规语言是上下文无关语言的特例。在上下文无关文法当中，只需三种规则，就能构筑任何一种正规语言：

1. A -> bB
2. A -> b
3. A -> Ø

UVa 464

Context-free Grammar 书写方式：Backus-Naur Form

个位数四则运算文法：
<expression> ::= <expression> <operator> <expression>
<expression> ::= "(" <expression> ")"
<expression> ::= "0" | "1" | "2" | "3" | "4" |
                 "5" | "6" | "7" | "8" | "9"
<operator> ::= "+" | "-" | "×" | "÷"

其他比较罕见的还有 Extended Backus-Naur Form、van Wijngaarden Form 等。

Parse / Evaluate

衍生过程画成树状图，成为“剖析树 Parse Tree”。

         |         | Parse Tree /         |
rule     | string  | Concrete Syntax Tree | Abstract Syntax Tree
---------| ------- | ---------------------| --------------------
         | S       |             S        |           ×  
S -> SAS | SAS     |          /  | \      |          / \ 
A -> ×   | S×S     |       S     A  S     |         +   1
S -> (S) | (S)×S   |     / | \   |  |     |        / \   
S -> 1   | (S)×1   |    (  S  )  ×  1     |       3   2  
S -> SAS | (SAS)×1 |      /|\             |
S -> 3   | (3AS)×1 |     S A S            |
S -> 2   | (3A2)×1 |     | | |            |
A -> +   | (3+2)×1 |     3 + 2            |

“剖析 parse”字串，就是在建立剖析树。“求值 evaluate”字串，就是在剖析树上面，以 bottom-up 顺序进行计算。

先前提到的“暧昧文法 ambiguous grammar”就是指：一个字串对应两种以上的 Parse Tree。换句话说：有两种以上的 Parse Tree 可以得到同一个字串。

rule     | string | parse tree
---------| -------| -------------
         | S      |          S   
S -> SAS | SAS    |      /   | \ 
S -> SAS | SASAS  |    S     A  S
(1st S)  |        |  / | \   |  |
S -> 1   | SA1AS  | S  A  S  -  3    ambiguous grammar
A -> -   | SA1-S  | |  |  |            ------------
S -> 7   | 7A1-S  | 7  ÷  1            | S -> SAS |
A -> ÷   | 7÷1-S  |                    | S -> (S) |
S -> 3   | 7÷1-3  |                    | S -> 0   |
                                       | S -> 1   |
rule     | string | parse tree         | ...      |
---------| -------| -------------      | S -> 9   |
         | S      |    S               | A -> +   |
S -> SAS | SAS    | /  |   \           | A -> -   |
S -> SAS | SASAS  | S  A     S         | A -> ×   |
(2nd S)  |        | |  |   / | \       | A -> ÷   |
S -> 1   | SA1AS  | 7  ÷  S  A  S      ------------
A -> -   | SA1-S  |       |  |  |
S -> 7   | 7A1-S  |       1  -  3
A -> ÷   | 7÷1-S  |
S -> 3   | 7÷1-3  |

UVa 10906 ICPC 3513

延伸阅读：四则运算的运算符号计算顺序

数学算式必须拥有明确的计算流程，不然每个人的计算结果都会不一样，永远得不到共识。也就是说，数学算式只能有唯一一种解读方式，不能是暧昧文法。

6÷2(1+2)=?
暧昧文法，导致出现两种解读方式。

6÷2×(1+2)=?
详细填入运算符号，只有唯一一种解读方式。

   6
------ = ?
2(1+2)
改成适当的运算符号，只有唯一一种解读方式。

数学算式除了必须详细填入运算符号之外，也必须严谨规定运算符号的结合顺序，才能杜绝暧昧文法。

“优先权 precedence”是指不同运算符号的结合顺序。例如先乘除、后加减。

“结合性 associativity”是指相同运算符号的结合顺序，普遍採用左结合（从左往右算）或者右结合（从右往左算）。例如加减乘除是左结合、次方是右结合。

precedence    | left associativity | right associativity
--------------| -------------------| -------------------
     +        |           +        |        ^           
    / \       |          / \       |       / \          
   1   ×      |         +   4      |      1   ^         
      / \     |        / \         |         / \        
     ^   4    |       +   3        |        2   ^       
    / \       |      / \           |           / \      
   2   3      |     1   2          |          3   4     
              |                    |                    
  1+2^3×4     |     1+2+3+4        |      1^2^3^4       
= 1+((2^3)×4) |   = ((1+2)+3)+4    |    = 1^(2^(3^4))

我们可以修改文法，让文法拥有优先权和结合性；当文法拥有优先权和结合性，就不是暧昧文法。

no precedence       | have precedence     | have precedence
no associativity    | no associativity    | have associativity
(ambiguous grammar) | (ambiguous grammar) | (not ambiguous grammar)
--------------------| --------------------| -----------------------
expr -> expr + expr | expr -> expr + expr | expr -> expr + term
expr -> expr × expr | expr -> term        | expr -> term
expr -> 1|2|...|9   | term -> term × term | term -> term × fact
                    | term -> 1|2|...|9   | term -> fact
                    |                     | fact -> 1|2|...|9
--------------------| --------------------| -----------------------
   expr             |      expr           |           expr       
   / | \            |    /   |   \        |        /    |     \  
expr + expr         | expr   +  expr      |     expr    +    term
  |    / | \        |   |       / | \     |     / | \          | 
  1 expr × expr     | term  expr  +  expr | expr  +  term    fact
      |    / | \    |   |     |        |  |   |      / | \     | 
      2 expr + expr |   1   term     term | term  term × fact  4 
          |      |  |       / | \      |  |   |     |     |      
          3      4  |    term × term   4  | fact  fact    3      
                    |      |     |        |   |     |            
                    |      2     3        |   1     2            
                    |                     |                      
     1+2×3+4        |      1+2×3+4        |      1+2×3+4         
   ≠ 1+(2×(3+4))    |    ≠ 1+((2×3)+4)    |    = (1+(2×3))+4

文法的左递迴导致左结合、右递迴导致右结合。

left recursion        | right recursion
& left associativity  | & right associativity
----------------------| -----------------------
(expr at left side)   | (fact at right side)
expr -> expr + term   | fact -> base ^ fact
expr -> term          | fact -> base
term -> 1|2|...|9     | fact -> 1|2|...|9
----------------------| -----------------------
            expr      |     fact               
            / | \     |     / | \              
        expr  +  term | base  +  fact          
        / | \      |  |   |      / | \         
    expr  +  term  4  |   1  base  +  fact     
    / | \      |      |        |      / | \    
expr  +  term  3      |        2  base  +  fact
  |        |          |             |        | 
term       2          |             3      base
  |                   |                      | 
  1                   |                      4 
      1+2+3+4         |       1^2^3^4
    = ((1+2)+3)+4     |     = 1^(2^(3^4))

延伸阅读：程式语言的运算子优先权

不同运算子之间，有固定的优先权；相同运算子之间，有固定的结合性： http://en.cppreference.com/w/cpp/language/operator_precedence 。

还有 Parse Tree 的最底层树叶，也必须考量计算顺序： http://en.cppreference.com/w/cpp/language/eval_order 。四则运算的 Parse Tree 最底层，都是确切数值，不必考量这种问题。

parse augment list of print_sum

        ,
       / \
      ,   get_b()
     / \
    ,   get_a()
   / \
++a   --b

在 C 语言规格书当中，此为 Unspecified Behavior。
无法确定++a、--b、get_a()、get_b() 谁先计算。

无法计算的问题！

判断 Context-free Grammar 是否正确生成给定的 Context-free Language。
判断 Context-free Grammar 是不是暧昧文法。
判断两种 Context-free Grammar 是否等价、生成同一种 Context-free Language。
计算两种 Context-free Language 的交集。

判断一种文法是否正确生成一套语言、判断一支程式是否有无穷迴圈，两者都是属于无法计算的问题。因此实务上我们只能设计文法、得到语言；无法设计语言、找出文法。

我们可以小心翼翼的设计文法，尽量避免暧昧文法，尽量让文法能够生成我们想要的语言；一如我们小心翼翼的设计程式，尽量避免无穷迴圈，尽量让程式能够生成我们想要的结果。

Context-free Language 的极限

正规语言处理循序文字，是字串匹配的终极武器。

上下文无关语言处理巢状文字，是程式语言的滥觞。

至于有哪些事情是上下文无关语言无法做到的呢？老实说我也不太清楚。交给各位研究吧！

Context-free Language: Recursive Descent Parser

演算法

剖析一个字串、建立 Parse Tree，有一个人人都懂的基础方法，就是穷举法。此演算法其实就是 Backtracking 而已，主要有两种穷举策略：

一、固定採用“左衍生 leftmost derivation”，穷举每次选中的规则。这个方式可能会造成无穷递迴。如果改用状态空间搜寻的 DLS、IDA*，就能避免无穷递迴。

二、先穷举字串的分割位置，从左端切下一段子字串；再穷举子字串的对应规则。

实作时，通常是一条规则就写一个函式，互相对应。呼叫 S()、传入原字串，就得到剖析结果。

UVa 134 171 293 586

范例：括号平衡

递迴分支只有一个，直接採用迴圈语法、辅以堆叠来实作，不必使用 Backtracking。

S -> [S] | (S) | SS | Ø

UVa 673 551 442

范例：多项式

一项一项剖析，直接採用迴圈语法，连堆叠都不用了。事实上这是正规语言。

UVa 126 327

范例：正整数四则运算，运算符号没有优先顺序。

由左到右一项一项剖析。事实上这是正规语言。

Context-free Language: Cocke-Younger-Kasami Algorithm

Context-free Grammar 结构格式：Chomsky Normal Form

一套语言可以设计各种不同的文法。为了让文法简洁易懂，就有人严谨地限定了文法的结构格式。比如 Chomsky Normal Form，文法规则只能是这两种格式：

1. A -> BC    （一个符号衍生两个符号）
2. A -> a     （一个符号衍生一个字元）

Context-free Grammar 很容易改写成 Chomsky Normal Form──凡是遇到符号太多、字元太多的规则，就分离成新规则。

grammar  | Chomsky Normal Form
---------| -------------------
S -> SAS | S -> SB
         | B -> AS
S -> (S) | S -> CD
         | C -> (
         | D -> SE
         | E -> )
S -> 0   | S -> 0
S -> 1   | S -> 1
...      | ...
S -> 9   | S -> 9
A -> +   | A -> +
A -> -   | A -> -
A -> ×   | A -> ×
A -> ÷   | A -> ÷

其他比较罕见的还有 Beta Normal Form、Greibach Normal Form、Kuroda Normal Form 等。

Chomsky Normal Form 与 Parse Tree

文法结构一旦改写成 Chomsky Normal Form，Parse Tree 就是一棵二元树，得以设计高效率的资料结构与演算法。

parse tree    | parse tree
              | (Chomsky Normal Form)
--------------| ---------------------
         S    |           S
      /  | \  |        /     \
   S     A  S |      S        B
 / | \   |  | |    /   \      /\
(  S  )  ×  1 |   C     D    A  S
  /|\         |   |   /  \   |  |
 S A S        |   (  S    E  ×  1
 | | |        |     / \   |
 3 + 2        |    S   B  )
              |    |   /\
              |    3  A  S
              |       |  |
              |       +  2

演算法

剖析一个字串，判断是否符合 Context-free Grammar。

首先将文法结构改写成 Chomsky Normal Form，再採用 Dynamic Programming：先穷举字串的对应规则；再穷举字串的分割位置，分割成左右两个子字串，连同对应符号，分别递迴下去。原始论文採用 bottom-up 实作方式。

时间複杂度为 O(T^3 * R)，T 为字串长度，R 为规则数量。

“ Matrix Chain Multiplication ”的演算法以及此演算法，两者的递迴关係非常相似。因为 Matrix Chain Multiplication 的演算法可以加速至 O(NlogN)，所以此演算法也许还可以加速。

奇技淫巧

bottom-up 实作方式当中，可以用文法规则等号右侧的两个符号，替文法规则建立二维索引表格。时间複杂度成为 O(T^3 * A^3)，其中 A 是符号种类数目。

A^3 是规则种类数目的上限，看似没有好处。但是当符号种类不超过 32 种，运用 int 当作集合的资料结构，让时间複杂度压至 O(T^3 * A^2)。当规则超过 A^2 条，就有好处。

UVa 10597

Context-free Language: Earley Parser

https://en.wikipedia.org/wiki/Earley_parser

Context-free Language: LL Parser（Under Construction!）

Top-down。

peek / pop

no precedence
1. expr -> expr + expr
2. expr -> expr × expr
3. expr -> x | y | z
4. expr -> ( expr )

no associativity
1. expr -> expr + expr
2. expr -> term
3. term -> term × term
4. term -> x | y | z
5. term -> ( expr )

left derivation
1. expr -> expr + term
2. expr -> term
3. term -> term × factor
4. term -> factor
5. factor -> x | y | z
5. factor -> ( expr )

right derivation, LL(1)
1. expr -> term termlist
2. termlist -> + term termlist
3. termlist -> λ
4. term -> factor factorlist
5. factorlist -> × factor factorlist
6. factorlist ->  λ
7. factor -> x | y | z
8. factor -> ( expr )

   expr             |    expr             |    expr             
   / | \            |    / | \            |    / | \            
expr + expr         | expr + expr         | expr + term         
  |    / | \        |   |      |          |   |      |          
  1 expr × expr     | term   term         |   1    term         
      |    / | \    |   |    / | \        |        / | \        
      2  ( expr )   |   1 term × term     |     term × term     
           / | \    |       |    / | \    |       |    / | \    
        expr + expr |       2  ( expr )   |       2  ( expr )   
          |      |  |            / | \    |            / | \    
          3      4  |         expr + expr |         expr + expr 
                    |           |      |  |           |      |  
      1+2×3+4       |         term   term |         term   term 
 ---> ((1+2)×3)+4   |           |      |  |
                    |           3      4  |           3      4

Context-free Language: LR Parser（Under Construction!）

Bottom-up。

Context-free Language: Sequitur Algorithm（Under Construction!）

http://en.wikipedia.org/wiki/Sequitur_algorithm

分享到QQ

分享到微博