标签: left-recursion

我正在尝试解决序言中的 DCG 语法并在一定程度上取得了成功，但我一直在评估涉及此类大括号的表达式。\nexpr( T, [\xe2\x80\x99(\xe2\x80\x99, 5, +, 4, \xe2\x80\x99)\xe2\x80\x99, *, 7], []),

expr(Z) --> num(Z).\nexpr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.\nexpr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.\nexpr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.\nnum(D) --> [D], {number(D)}.\n\neval(L, V, []) :- expr(V, L, []).\n

我试图匹配一些句子(例如001 [0,0,1],(1 +(1/0))['(',1,+,'(',1,/,0,')' ,')'], 等等.

我已经让自己跟随小型DCG了.

g3 --> s3.
s3 --> e3.

e3 --> eAdd.
e3 --> eMin.
e3 --> eMul.
e3 --> eDiv.
e3 --> n3.

eAdd --> ['('],e3,['+'],e3,[')'].
eMin --> ['('],e3,['-'],e3,[')'].
eMul --> ['('],e3,['*'],e3,[')'].
eDiv --> ['('],e3,['/'],e3,[')'].


n3 --> d3.
n3 --> n3,d3.
d3 --> [0].
d3 --> [1].

现在我的问题是,它与使用 - ,*或/的句子不匹配,但它仅适用于使用+的递归句子.

例如:

phrase(g3,['(',1,'+','(',1,'+',1,')',')']).

会工作,但是

phrase(g3,['(',1,'+','(',1,'/',1,')',')']).

不行.

任何帮助将不胜感激,谢谢!

我一直在尝试使用scala-parser-combinator库构建一个SQL解析器，我已将其大大简化为以下代码。

class Expression
case class FalseExpr() extends Expression
case class TrueExpr() extends Expression
case class AndExpression(expr1: Expression, expr2: Expression) extends Expression

object SimpleSqlParser {
  def parse(sql: String): Try[Expression] = new SimpleSqlParser().parse(sql)
}

class SimpleSqlParser extends RegexParsers {
  def parse(sql: String): Try[_ <: Expression] = parseAll(expression, sql) match {
    case Success(matched,_) => scala.util.Success(matched)
    case Failure(msg,remaining) => scala.util.Failure(new Exception("Parser failed: "+msg + "remaining: "+ remaining.source.toString.drop(remaining.offset)))
    case Error(msg,_) => scala.util.Failure(new Exception(msg))
  }

  private def expression: Parser[_ <: Expression] =
    andExpr | falseExpr | …

我正在尝试实现一个带有一组形式为{a,b,c,d}*的字符串的dcg.我遇到的问题是如果我有一个形式s的查询([a,c,b], []),它返回true,这是正确的答案但是当我有一个形式s([a,c,f],[])的查询时,它不返回一个答案,它用完了本地堆栈.

s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].

我很遗憾再问一个关于相互左递归的问题,我觉得我的情况是独一无二的,或者至少我无法弄清楚它是否与其他人的语法联系起来.我对comp sci世界有点新鲜(我在java中自学,这是我的目标语言,现在是ANTLR4)所以如果可能的话请用layperson术语描述,而不是CS主要术语.

我正在编写一个需要代数和符号衍生物的程序,当然这需要对事物进行解析,然后对树进行操作,但我甚至不会担心这一点,因为我认为ANTLR4支持直接左递归,但是显然它不是以某种方式.在输出中,它一直告诉我,我的方法[表达式]是相互遗留的,显然是不允许的......？我的问题:

1)有人可以解释左递归/相互和直接左递归之间的区别,如果有的话？

2)解释我的语法中是什么导致了这种递归烦恼,以及如何解决它？而且我不确定这是否是主题:

3)人们说关于替代品和标签替代品的事情(我认为他们的意思是#label符号).那个有什么用？

grammar MathProcessor;
@header {package utils;}
END: ';';
EQUALS: '=';
SIN: 'sin(';
COS: 'cos(';
TAN: 'tan(';
SEC: 'sec(';
CSC: 'csc(';
COT: 'cot(';
LN: 'ln(';
EPOW: 'pow(';
RPAREN: '(';
LPAREN: ')';
EXP: '^';
MULT: '*';
DIV: '/';
ADD: '+';
SUBT: '-';
VAR: ('a'..'z'|'A'..'Z');
INT: ('0'..'9')+;
mathobj: ((equation|expression) END) EOF;
equation: (expression '=' expression);

expression: 
((RPAREN|SIN|COS|TAN|SEC|CSC|COT|LN|EPOW) expression (RPAREN)) #parenOps
| (expression EXP expression) #exponent
| (expression (MULT|DIV) expression) #multiplyDivide 
| (expression (ADD|SUBT) expression) #addSubtract
| (VAR|INT) #varInt …

我正在尝试在 prolog 中编写一些 dcg 语法，它将描述
a^nb^n n>=0
"",ab,aabb,aaabbb itd

我写的都是

s --> slowo.
slowo --> [a],slowo,[b],!.
slowo --> [].  

只要我想做的只是检查单词是否正确，它就很好，但是 dcg 语法应该如何在 prolog 中查找，以便?-phrase(s,X)从我的语言中生成所有单词？

我正在尝试编写一个lambda演算解析器,我定义的语法似乎不在LLR中:

E ::= x | \x.E | EE | (E)

我减少左递归:

E ::= xE' | \x.EE' | (E)E'
E'::= EE' | <empty>

似乎不对,有人可以帮忙吗？