解析连续的非终端

Question

我知道我应该有 T-> UU，第一个 parse_U 只解析“aabb”，第二个 parse_U 只解析最后一个“ab”，但我不知道如何使用追加来做到这一点。我只能检索以a开头并以b结尾的子列表，但这不是我想要的结果。

如有任何帮助，我们将不胜感激。

Answer 1

对于 Prolog 中的解析，我建议在可用时使用 DCG（明确子句文法）。

如果我没记错的话，你的语法可以简单地变成

isS --> isT.
isS --> isV.

isT --> isU, isU.

isU --> [a], isU, [b].
isU --> [a, b].

isV --> [a], isV, [b].
isV --> [a], isW, [b].

isW --> [b], isW, [a].
isW --> [b, a].

并可用于调用 isS(L, [])，其中 L 是包含要解析的序列的列表。

正在调用

isS([a,a,b,b,a,b], [])

你应该得到 true。

--- 编辑 ---

this is homework and we are not allowed to use "-->"

DGC（使用-->）语法没有什么特别之处；这只是常用语法的简化。

如果我没记错的话，你可以将上面的 DCS 语法写成（注意：在规则名称中添加下划线）

is_S(Lin, Lout) :- is_T(Lin, Lout).
is_S(Lin, Lout) :- is_V(Lin, Lout).

is_T(Lin, Lout) :- is_U(Lin, Lmid), is_U(Lmid, Lout).

is_U([a | Tin], Lout)      :- is_U(Tin, [b | Lout]).
is_U([a, b | Lout], Lout).

is_V([a | Tin], Lout)      :- is_V(Tin, [b | Lout]).
is_V([a | Tin], Lout)      :- is_W(Tin, [b | Lout]).

is_W([b | Tin], Lout)      :- is_W(Tin, [a | Lout]).
is_W([b, a | Lout], Lout).

通话中

is_S([a,a,b,b,a,b], [])

你应该得到 true。

解析连续的非终端

Parsing consecutive non-terminals

context-free-grammar