LR(0)文法相关内容总结

一、 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	+	-	*	/	(	)	$
E -> · E + E	S1					S6
E -> · E - E	S2					S6
E -> · E * E	S3					S6
E -> · E / E	S4					S6
E -> · ( E )	S7					S6
E -> · id	S5					S6
E -> E · + E		S9	S10				R1	R1
E -> E · - E		S9	S10				R2	R2
E -> E · * E				S11	S12		R3	R3
E -> E · / E				S11	S12		R4	R4