java - 在 ll(1) 中检查一种语法与另一种语法的算法

Question

我需要一个算法来检查 G1 的语言是否是 G2 语言的子集。 (假设 G1 和 G2 是两个具有相同字母表的 LL(1) 语法，其产生规则为 A-->aB 或 A-->a 形式，并且“a”是非 epsilon。我有一个解析算法根据字符串检查语法，但不检查另一种语言。有没有人有解决方案。

Answer 1

你的语法看起来很规律。所以算法就是将语法转换为NFA。这是一个简单的 1-1 映射。然后通过子集构造将 NFA 转换为 DFA。称它们为A和B。分析它们很容易确定L(A)子集吗？磅)。例如，由于有众所周知的有效算法来确定 L(A) ==? L(B) 并构造一个接受 L(A) 交集 L(B) 的新机器 I(A,B)，只需计算

( L(I(A,B)) ==? L(A) )  or  ( L(I(A,B)) ==? L(B) )