一、 LR(0)文法
1、LR(0)文法的定義：
LR(0)文法是一種特殊的上下文無關文法，它滿足在任何情況下，只有一個產生式可以被用于歸約。
2、LR(0)文法的核心：
a、先進先出原則。需保證最新歸約的串不會被前面的串覆蓋掉。 b、通過構造自動機實現分析。 c、構造出的自動機可以用來檢查輸入串是否符合文法。如果符合，則自動機會從起始狀態走到接受狀態。
3、LR(0)文法的本質：
LR(0)文法的核心是使用狀態機，即使用有限狀態自動機的方法來檢查輸入串是否符合文法。
二、 LR(0)文法的goto下步
1、goto下步的定義：
goto下步意味著從文法中某個產生式A->α·Bβ，以 B 為條件跳轉到其他狀態。
2、goto下步的實現：
a、確定狀態機。 b、從某個狀態 i，輸入一個 B，跳轉到狀態 j。
3、goto下步的本質：
goto下步本質上是通過狀態機的跳轉，來構建接下來的新的狀態機。
三、 LR(0)文法分析表構造方法
1、LR(0)文法分析表的定義：
LR(0)文法分析表是一個二維表格，它包含所有狀態和所有的終結符號，以及在任何狀態和任何終結符號下，應該採取的動作。
2、LR(0)文法分析表的構造方法：
a、先構造狀態機，並標註每個狀態的產生式或者規則。 b、對規則進行分析，將狀態機分成兩部分：內核（有沒有歸約),和外部（歸約）。 c、使用我們的「CLOSURE」演算法，確定每個狀態中的規則（產生式）。 d、構造出 LR(0) 分析表，它包含了文法中所有符號的行和狀態的列。 e、使用狀態機和分析表，按照指定的規則進行分析。
3、LR(0)文法分析表構造方法的本質：
LR(0)文法分析表的構造本質是通過自動機的狀態和轉移信息，把文法的產生式、符號、以及可接受的動作編碼成表格，以便分析字元串的過程中做出準確的決策，以便完成分析過程。
四、 LR(0)分析表
1、LR(0)分析表的定義：
LR(0)分析表是由狀態機自動構建的，在表中每一個格子里，都有一個動作或者是一個狀態。
2、LR(0)分析表的實現：
a、用狀態機跑文法，並用狀態機檢查每個輸入字元，直到達到結束狀態。 b、在狀態機中跟蹤歸約使用的產生式，以及接受的終結符號的ID。 c、檢查每個輸入字元，根據分析表中的規則，採取相應的操作，直到完成分析過程。
3、LR(0)分析表的本質：
LR(0)分析表的本質是構建一個狀態機，按照文法中定義的規則，將狀態機從起始狀態依照輸入字元的變化進行跳轉，直到達到接受狀態，以完成語法分析。
五、LR(0)文法歸約後
1、LR(0)文法歸約的定義：
在語法分析器中，將代表某個非終結符的符號串替換為該非終結符的產生式右部。
2、LR(0)文法歸約的實現：
a、根據分析表中的規則，歸約文法中的符號串。 b、對於 LR0-1 語法，每次在棧中彈出一個符號。
3、LR(0)文法歸約後的本質：
LR(0)文法的歸約本質是利用狀態機跳轉和替換符號串來實現對文法的規約和分析。
六、LR(0)分析表重複怎麼辦
1、LR(0)分析表重複的定義：
當某個項目在內核中已經存在，但其狀態還未追溯狀態時，就會導致文法的重複。
2、LR(0)分析表重複的解決方法：
a、將重複的狀態合併，將相同的狀態都合併為一個。 b、通過合併操作，使分析表更為簡潔。
3、LR(0)分析表重複的本質：
LR(0)分析表重複的本質是在進行語法分析的時候，同一狀態下存在不同的歸約操作。通過合併操作，將同一狀態下可以採取的動作合併統一，以便更為準確地實現分析。
七、LR(0)與LRO(3)的區別
1、LR(0)與LRO(3)的定義：
LR(0)和LRO(3)均為上下文無關文法，但兩者不同。
2、LR(0)與LRO(3)的區別：
a、LR(0)僅僅規定了一個基本的操作策略，而LRO(3)則規定了更多的操作策略。 b、LR(0)的限制比較少，LRO(3)在語法分析器的生成、分析表構造演算法、以及分析過程中都比LR(0)複雜得多。 c、更高級的語法分析演算法通常需要支持文法中的操作，而LR(0)並不提供此功能。
3、LR(0)與LRO(3)的本質：
LR(0)的本質是構建一個狀態機，僅有一種操作策略；LRO(3)則是在LR(0)的基礎上，增強了演算法的處理能力和操作策略，以實現更高級別的語法分析。
八、LR(0)文法分析實例
以一個簡單的四則運算為例，簡單地描述一下LR(0)文法的分析步驟。
步驟一：分析我們將使用的符號表，即文法中的終結符和非終結符。通常情況下，所有終結符都以小寫字母表示，而非終結符則以大寫字母表示。non-terminals = { E }
terminals = { +, -, *, /, (, ), id, $ }步驟二：為文法中的每個非終結符確定所有的產生式。
E -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> ( E )
E -> id步驟三：構建 LR(0)項。
E -> · E + E
E -> · E - E
E -> · E * E
E -> · E / E
E -> · ( E )
E -> · id步驟四：使用 「CLOSURE」 演算法，對於每個已有的 LR(0)項，找到所有可能的後繼關係項。
Closure(E -> · E + E)={E -> E· + E, E -> · E + E,E -> · E - E,E -> · E * E,E -> · E / E,E -> · ( E ),E -> · id}
Closure(E -> · E - E)={E -> E· - E, E -> · E + E,E -> · E - E,E -> · E * E,E -> · E / E,E -> · ( E ),E -> · id}
Closure(E -> · E * E)={E -> E· * E, E -> · E + E,E -> · E - E,E -> · E * E,E -> · E / E,E -> · ( E ),E -> · id}
Closure(E -> · E / E)={E -> E· / E, E -> · E + E,E -> · E - E,E -> · E * E,E -> · E / E,E -> · ( E ),E -> · id}
Closure(E -> · ( E ))={E -> · E + E,E -> · E - E,E -> · E * E,E -> · ·E / E,E -> · ( E ),E -> · id}
Closure(E -> · id)={E -> · E + E,E -> · E - E,E -> · E * E,E -> · E / E,E -> · ( E ),E -> · id}步驟五：針對所有的 LR(0)項構造出狀態機。
| State | Action | Goto
--|--------|------------------------|----------------
0 | E -> · E + E $ | [Shift,1] E
1 | E -> E · + E $ | [Reduce,E -> id]
2 | E -> E · - E $ | [Reduce,E -> id]
3 | E -> E · * E $ | [Reduce,E -> id]
4 | E -> E · / E $ | [Reduce,E -> id]
5 | E -> ( · E ) $ | [Shift,8] (
6 | E -> · ( E ) | [Shift,9] (
7 | E -> · id | [Shift,6] id
8 | E -> ( E · ) $ | [Reduce,E -> id]
9 | E -> ( · E ) | [Shift,8] (步驟六：最終的 LR(0)分析表。
| Production | id | + | - | * | / | ( | ) | $ |
--|---------------------|----|----|----|----|----|----|----|----|
0 | E -> · E + E | S1 | | | | | S6 | | |
1 | E -> · E - E | S2 | | | | | S6 | | |
2 | E -> · E * E | S3 | | | | | S6 | | |
3 | E -> · E / E | S4 | | | | | S6 | | |
4 | E -> · ( E ) | S7 | | | | | S6 | | |
5 | E -> · id | S5 | | | | | S6 | | |
6 | E -> E · + E | | S9 | S10| | | | R1 | R1 |
7 | E -> E · - E | | S9 | S10| | | | R2 | R2 |
8 | E -> E · * E | | | | S11| S12| | R3 | R3 |
9 | E -> E · / E | | | | S11| S12原創文章，作者：RIFUZ，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/331687.html
微信掃一掃 
支付寶掃一掃 