文法定義編譯原理
❶ 編譯原理中 文法 文法G定義為四元組(Vn ,Vt,P,S)這4個是什麼意思 另外 終結符和非終結符是什麼意思
文法G是一個四元式(Vt,Vn,S,P)
其中Vt是一個非空有限集,它的每個元素稱為終結符號
Vn是一個非空有限集,它的每個元素稱為非終結符號(Vt和Vn的交集為空)
S是一個非終結符號,稱為開始符號
P是一個產生式集合(有限),每個產生式的形式是P-->a
開始S必須在某個產生式的左部出現一次
終結符指組成語言的基本符號(如基本字、標識符、常數、算符、界符)
非終結符號(也稱語法變數)表示一定符號串的集合。
你看到小寫字母一般是終結符,大寫字母肯定是非終結符
不明白可以聯系。
❷ 編譯原理中的語法和文法一樣嗎
編譯原理中的語法和文法是不一樣的,但卻融會貫通。
在計算機科學中,文法是編譯原理的基礎,是描述一門程序設計語言和實現其編譯器的方法。
文法分成四種類型,即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。
形式語言,這種理論對計算機科學有著深刻的影響,特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作用。
多數程序設計語言的單詞的語法都能用正規文法或3型文法(3型文法G=(VN,VT,P,S)的P中的規則有兩種形式:一種是前面定義的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一種形式是:A→Ba或A→a,前者稱為右線性文法,後者稱為左線性文法。正規文法所描述的是VT*上的正規集)來描述。
四個文法類的定義是逐漸增加限制的,因此每一種正規文法都是上下文無關的,每一種上下文無關文法都是上下文有關的,而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。
❸ 編譯原理的文法
「文法是以有窮的集合刻畫無窮的集合的一個工具」,有窮的集合應該是已經出現的,人們普遍接受的詞、片語或句子,無窮的集合就是有窮的集合的詞、片語或句子,創造新的集合過程和結果,有待進一步認識接受。
我們的文法規定內涵是已經明確定義的和正在定義(聲明)的內容。反映到計算機語言程序中就是編程時已經定義的和正在定義(聲明)的字元或字元串。文法可以以表的形式,或詞典形式存放。
❹ 什麼是編譯原理
編譯原理是計算機專業的一門重要專業課,旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。 編譯原理是計算機專業設置的一門重要的專業課程。雖然只有少數人從事編譯方面的工作,但是這門課在理論、技術、方法上都對學生提供了系統而有效的訓練,有利於提高軟體人員的素質和能力。
這門課程關注的是編譯器方面的產生原理和技術問題,似乎和計算機的基礎領域不沾邊,可是編譯原理卻一直作為大學本科的 必修課程,同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個演算法問題而已,當然由於這個問題十分復雜,其解決演算法也相對復雜。 我們學的數據結構與演算法分析也是講演算法的,不過講的基礎演算法,換句話說講的是演算法導論,而編譯原理這門課程講的就是比較專註解決一種的演算法了。在20世紀 50年代,編譯器的編寫一直被認為是十分困難的事情,第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時,誕生了許多跟 編譯相關的理論和技術,而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣,雖然沒有最終解決問題,但是其間 誕生不少名著的相關數論。
❺ 編譯原理-文法定義
文法定義公式如下:
Chomsky 文法分類將文法分為四種,0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。
又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法(Phrase Structure Grammar)
定義: 對於產生式 α→β , α 至少包含一個非終結符。
為什麼要叫無限制文法,明明它要求產生式的左部必須包含一個非終結符。
又被稱為上下文有關文法(Context-Sensitive Grammar)
定義:對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外
為什麼叫做上下文有關文法?
一般情況下,這種產生式的形式為 α1Aα2→α1βα2
又被稱為上下文無關文法(Context-Free Grammar)
定義:對任一產生式 α→β ,都有 α∈VN,β∈(VN∪VT)*
為什麼叫上下文無關文法?
又被稱為正則文法(Regular Grammar,RG),分為右線性(Right Linear)文法和左線性(Left Linear)文法。
定義: 對任一產生式 α→β ,都有 α∈VN,β最多兩個字元元素,如果有二個字元必須是(終結符+非終結符)的格式,如果是一個字元,那麼必須是終結符。
根據產生式右部非終結符位置不同,分為右線性文法和左線性文法。
可以看出,不同文法就是對產生式進行逐層的限制,所以各個文法是包含關系,即0型文法包含1型文法;1型文法又包含2型文法;2型文法最後包含3型文法。
❻ 什麼是文法(編譯原理)
【定義】
文法G定義為四元組(VN,VT,P,S)
其中 VN :非終結符號(即語法變數)集
VT : 終結符號集
VN∩VT =Φ,令V= VN∪VT,V稱為文法G的字母表或字匯表。
P :產生式(α→β)集
S :開始符號,且S∈VN ,S至少要在一條規則的左部出現。
【約定】
一般地,文法G的 四元組 不用全部給出 ,而只將產生式寫出。
約定:
(1)第一條產生式的左部是開始符號
(2)用尖括弧括起來的(或 大寫字母 )是非終結符號
(3)不用尖括弧括起來(或 小寫字母 )是終結符號
(4)還有一種習慣寫法,即 G[S] ,其中 S 是 開始符號 。
【舉例】
例: G=(VN,VT,P,S)
其中 VN={S},
VT ={0,1},
P={S→0S1,S→01}
S是開始符號