2016/10/27 Formal Language

花了一小時複習上一堂課的內容
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

- - -

• Parsing and Ambiguity [ pdf ]  HW5.2 [ pdf ]

• Context-Free Grammars and Programming Languages (Skipped)

• Chap 6 Simplification of Context-Free Grammars and Normal Forms

• Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]

- - -

參考網址: http://www.csie.ntnu.edu.tw/~u91029/Language.html
發現這網址不錯, 講得蠻細的!

- - -

ch 5-1

• Parsing: 判斷一個string是不是屬於一個Grammar
• 題型: 給一個Grammar,  寫出Language的表示方式
• 一套 Language 可以設計許多種不同的 Grammar 。
• Grammar 理論上必須剛好生成 Language 之內的所有字串、永不生成 Language 以外的所有字串。
• Left/Right-most derivation: 最左/右邊的variable先做
• Derivation(Parse) Tree:

• First node should be root(S)

• every leaf should be terminal.(a,b...)

• every internal node should be variable(A,B...)

• leaf can allow variable

• Partial Derivation Tree:
• sub-tree of  Derivation Tree

- - -

ch 5-2

• s-grammar: 滿足A->ax形式, 且任何(A,a)pair都只出現一次的grammar
• 參考 : http://cs.stackexchange.com/questions/1958/relation-between-simple-and-regular-grammars
• A Simple Grammar (s-grammar) is one in which every production is of the form A→aB1B2...Bn$A\to a{B}_1{B}_2...B_n$ where a$a$ is a terminal and all Bi,i≥0$B_i,i\ge 0$ are non-terminals, and there is only one production with any pair ⟨A,a⟩$⟨A,a⟩$.
• 
  
• Ambiguous
• 我們可以「剖析 Parse 」一個字串，逐字對應至 Grammar 、確立語法，進而判斷原本字串是不是 Language 當中的字串。
• 字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法 Ambiguous Grammar 」。

- - -

Formal Language 四大類型

• Regular Language
• Context-free Language: 一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。「上下文無關」是指符號不會連帶上下文一起衍生。也就是每條規則的左式，只有一個符號，而不會連帶其他符號和字元。
• Context-sensitive Language
• Unrestricted Language

四種語言規律，由規律嚴謹到規律寬鬆排列，前者是後者的特例。

其中 Regular Language 與 Context-free Language ，由於規律十分嚴謹，所以得以設計效率極高的演算法、擁有實務價值。

例如 Regular Language 用於字串匹配、用於驗證字串格式。例如 Context-free Language 用於設計程式語言、用於檢索網頁資料。

- - -