我需要一个算法来检查 G1 的语言是否是 G2 语言的子集。 (假设 G1 和 G2 是两个具有相同字母表的 LL(1) 语法,其产生规则为 A-->aB 或 A-->a 形式,并且“a”是非 epsilon。我有一个解析算法根据字符串检查语法,但不检查另一种语言。有没有人有解决方案。
最佳答案
你的语法看起来很规律。所以算法就是将语法转换为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) )
关于java - 在 ll(1) 中检查一种语法与另一种语法的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34383584/