• 正則語法

    編輯
    本詞條由“匿名用戶” 建檔。

    什么是正則語法

    編輯

    在理論計算機科學形式語言理論中,正則語法是一種右正則或左正則的語法。雖然它們的確切定義因教科書而異,但它們都要求所有的生成規則最多只有一個非終端符號;這個符號要么總是在規則的右邊的末尾,要么總是在規則的開頭。每個規則語法都描述一種規則語言

    嚴格的正則語法

    編輯

    右正則語法(也叫右線性語法)是一個形式化的語法(N,Σ,P,S),其中P中的所有生產規則都是以下形式之一。A→aA→aBA→ε其中A、B、S∈N為非終端符號,a∈Σ為終端符號,ε表示空字符串,即長度為0的字符串,S稱為起始符號。在左規則語法(也叫左線性語法)中,所有的規則都服從于以下形式A→aA→BaA→ε一個給定的語法所描述的語言是所有字符串的集合,這些字符串只包含終端符號,并且可以通過重復應用生產規則從起始符號衍生出來。這兩種規則不能混用,例如,規則集為{S→aT,T→Sb,S→ε}的語法是沒有規則的,它描述的語言{aibi:i∈N{displaystyle/mathbb{N}.}},這也是不規則的。一些教科書和文章不允許空的生產規則,并假定語言中不存在空字符串。

    擴展的正則語法

    編輯

    一個擴展的右正則語法是指所有的規則都服從于以下的一個規則A→w,其中A是N中的一個非終端,w在一個(可能是空的)終端字符串中Σ*A→wB,其中A和B在N中,w在Σ*中。一些作者把這種類型的語法稱為右規則語法(或右線語法),上面的類型稱為嚴格右規則語法(或嚴格右線語法)。一個擴展的左規則語法是指所有規則都服從下列規則之一的語法A→w,其中A是N中的一個非終端,w在Σ*中A→Bw,其中A和B在N中,w在Σ*中。例子一個右規則語法G的例子,N={S,A},Σ={a,b,c},P由以下規則組成S→aSS→bAA→εA→cA而S是起始符號。這個語法描述了與正則表達式a*bc*相同的語言,即由任意多的as組成的所有字符串的集合,后面是一個b,后面是任意多的cs。對于同一正則表達式,一個稍長但更明確的擴展右正則語法G由N={S,A,B,C},Σ={a,b,c}給出,其中P由以下規則組成。S→AA→aAA→BB→bCC→εC→cC...其中每個大寫字母對應于正則表達式中下一個位置開始的短語。作為編程語言領域的一個例子,表示浮點數的所有字符串的集合可以用一個擴展的右規則語法G來描述,N={S,A,B,C,D,E,F},Σ={0,1,2,3,4,5,6,7,8,9,+,-,.,e},其中S是起始符號,P由以下規則組成。表達能力在(嚴格的)右規則語法的規則和非確定性有限自動機的規則之間有一個直接的一對一的對應關系,這樣的語法正好產生自動機接受的語言。因此,右正則語法正好生成所有正則語言

    正則表達式

    左規則語法描述了所有這類語言的反面,也就是說,也正好是規則語言。每個嚴格的右正則語法都是擴展的右正則語法,而每個擴展的右正則語法都可以通過插入新的非端點而變得嚴格,從而產生相同的語言;因此,擴展的右正則語法也產生常規語言。類似地,擴展的左規則語法也是如此。如果不允許有空的生成,那么只有不包括空字符串的所有規則語言才能被生成。雖然正則語法只能描述正則語言,但反之亦然:正則語言也能被非正則語法所描述。

    混合左規則和右規則

    編輯

    如果允許混合左規則和右規則,我們仍然有一個線性語法,但不一定是一個規則語法。更重要的是,這樣的語法不需要生成規則語言:所有的線性語法都可以很容易地變成這種形式,因此,這種語法正好可以生成所有線性語言,包括非規則語言。例如,語法G有N={S,A},Σ={a,b},P有起始符號S和規則{displaystyle{a{i}b{i}:igeq0}},典型的非規則線性語言。,是典型的非規則線性語言。

    內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164076/

    (0)
    詞條目錄
    1. 什么是正則語法
    2. 嚴格的正則語法
    3. 擴展的正則語法
    4. 混合左規則和右規則

    輕觸這里

    關閉目錄

    目錄
    91麻精品国产91久久久久