第四章文法和語言-資料下載頁

　　

【正文】 → a 89 消除一般左遞歸 要求文法 : (A(=+(A) （ 1） .以某種順序將文法非終結符排列 A1 ,A2 …An （ 2） for i:=1 to n do begin for j:=1 to i1 do 用 Ai?1| ?2r…| ? k r替代 形如 Ai Ajr的規則 ,其中 Aj ?1| ?2…| ?k是關于 Aj的全部產生式 。 消除 Ai規則的直接左遞歸 。 end。 （ 3） 化簡由 2得到的文法 90 化簡文法 文法實用中的一些說明 文法中 不含有 有害規則 和 多余規則 有害規則 ：形如 U→ U的產生式。會 引起 文法的 二義性 多余規則 ：指文法中 任何句子的推導 都 不會用到的規則 文法中 不含有 不可到達和不可終止的 非終結符 1）文法中某些 非終結符不在任何規則的右部出現 ，該非終結符稱為 不可到達 。 2）文法中某些 非終結符 ，由它 不能推出終結符號串 ，該非終結符稱 為 不可終止 。 91 對于文法 G[S]，為了保證任一非終結符 A在句子 推導中出現，必須滿足如下兩個條件： 1. A必須在某句型中出現 即有 S =* αAβ，其中 α， β屬于 V* 2. 必須能夠從 A推出終結符號串 t來 即 A =* t，其中 t∈ VT* 92 化簡文法 ?例： G[S] ： 1) S→ Be 2) B→ Ce D為不可到達 3) B→ Af C為不可終止 4) A→ Ae 5) A→ e 6) C→ Cf 7) D→ f 產生式 2）， 6）， 7）為 多余規則 應去 掉。 93 上下文無關文法中的 ε規則 上下文無關文法中某些規則可具有形式 A→ ε，稱這種規則為 ε規則 因為 ε規則會使得有關文法的一些討論和證明變得復雜 ,有時會限制這種規則的出現 兩種定義的唯一差別是 ε句子在不在語言中 文法構思的啟示是要找出語言的有窮描述，而如果語言 L有一個有窮的描述，則 L1=L∪ ｛ ε｝也同樣有一個有窮的描述，并且可以證明，若 L是上下文有關語言、上下文無關語言或正規語言，則L∪ ｛ ε｝和 L｛ ε｝分別是上下文有關語言、上下文無關語言和正規語言。 94 思考 本章目的為語言的語法描述尋求工具 ,以便： 對源程序給出精確無二義的語法描述。（嚴謹、簡潔、易讀） 根據語言文法的特點來進行語法分析 從描述語言的文法可以自動構造出可用的分析程序 制導語義翻譯 ,什麼是它的語言 ? ? ? 95 [本章小結 ] ,應重點理解文法 ,推導 ,句型句子及語言的定義等概念 .語法分析有關內容在后面章節會詳細討論 . ,它用 規則只能陳述的是 :語言的所有句子以什麼樣的符號串能出現 .請記住 文法和語言的形式定義中的 “形式”的含義 — 只涉及 語言的語法不涉及語言的語義 . .形式語言理論是對符號串集合的表示法 、 結構及其特性的研究 。是程序設計語言語法分析研究的基礎 。 [本章小結 ] 考察本章知識點最典型的題目是 G[A]，寫出它定義的語言描述 如： G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案 :G[A]定義的語言由 0、 1符號串組成，串中 0和 1的個數相同 . ，構造文法 . 如：構造一文法 ,其定義的語言是由算符 +, *, (,)和運算對象 a構成的算術表達式的集合 . 答案 1: G[E] E→E+T|T T→T*F|F F→(E)|a 答案 2: G[E] E→E+E|E*E|(E)|a 97 相關術語的回顧（ 英 文版） 上下文無關文法 A context free grammar(grammar for short) consists of terminals ,nonterminals,a start symbol,and productions. Terminals are the basic symbols from which strings are formed. Nonterminals are syntactic variables that denote sets of strings that help define the language generated by the grammar. In a grammar,one nonterminal is distinguished as the start symbol,and the set of strings it denotes is the language defined by the grammar. The productions of a grammar specify the manner in which the terminals and nonterminals can be bined to form string. 98 句型句子和語言 Given a grammar G with start symbol S,we can use the =* relation to define L(G),the language generated by G. Strings in L(G) may contain only terminal symbols of G. We say a string of terminals w is in L(G) if and only if S =* w .The string w is called a sentence of G. If S =* α,wher α may contain nonterminals then we say that α is a sentential form of G 99 驗證文法生成的語言 A proof that a grammar G generates a language L has two parts:we must show that every string generated by G is in L,and coversely that every string in L can indeed be generated by G. 100 語法樹和推導 A parse tree may be viewed as a graphical representation for a derivation that filt out the choice regarding replacement order. The leaves of the parse tree are labeled by nonterminals or terminals and ,read from left to right,they constitute a sentential form,called the yield or frontier of the tree. 101 句型分析，語法分析 Parsing is the process of determing if a string of token can be generated by a grammar. Most parsing methods fall into one of two classes,called the topdown and bottomup methods. These terms refer to the order in which nodes in the parse tree are the former,construction starts at the root and proceeds towards the leaves,while,in the later,construction starts at the leaves and proceeds towards the root. 102 二義性 A grammar that produces more than one parse tree for some setence is said to be ambiguous. Put another way, an ambiguous grammar is one that produces more than one leftmost or more than rightmost derivation for the same sentence. Sometimes an ambiguous grammar can be rewritten to eliminate the ambiguity. For exmple suitable grammars for expression can often be constructed using associativity and precedence information ,as in the slide74 103 消除左遞歸規則 A grammar is left recursive if it has a nonterminal A such that there is a derivation A =+ Aα for some string α . A leftrecursive production is like:A →A α in which the leftmost symbol on the right side is the same as the nonterminal on the left side. The general case is that a nonterminal A with two productions A →A α | β where α and β are sequences of terminals and nonterminals that do not start with A. And the left recursive pair of productions A →A α | β could replaced by the nonleftrecursive productions: A → β A’ A’ → α A’| ε Here A’ is a new nonterminal. The production A’ → α A’ is right recursive. 104 練習 1. 寫一文法，使其語言是偶正整數的集合。 要求： (1) 允許 0打頭 (2) 不允許 0打頭 G［ 〈 表達式 〉 ］是二義的。 〈 表達式 〉 ∷ =a|(〈 表達式 〉 )|〈 表達式 〉〈 運算符 〉〈 表達式 〉 〈 運算符 〉 ∷ =+||*|/ 3. 令文法 G［ E］為： E→T|E+T|E T T→F|T*F|T/F F→(E)|i 證明 E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。 105 練習 4. 給出生成下述語言的上下文無關文法： （ 1） { anbnambm| n， m=0} (2) { 1n0m 1m0n| n， m=0} 5. 給出生成下述語言的三型文法： (1) { anbm|n,m=1 } (2){anbmck|n,m,k=0 } 6. 給出下述文法所對應的正規式： S→0A|1B A→1S|1 B→0S|0