标签: recursive-descent

我最近正在努力教自己解析器(语言/无上下文语法)是如何工作的,除了一件事以外,大部分解析器似乎都有意义.我特别关注LL(k)语法,其中两个主要算法似乎是LL解析器(使用堆栈/解析表)和递归下降解析器(简单地使用递归).

据我所知,递归下降算法适用于所有LL(k)语法,可能更多,而LL解析器适用于所有LL(k)语法.然而,递归下降解析器显然要比LL解析器简单得多(正如LL一个比LR一个简单).

所以我的问题是,使用任何一种算法时可能遇到的优点/问题是什么？为什么有人会选择LL而不是递归下降,因为它适用于同一组语法并且实现起来比较棘手？

我试图使用Powershell 2.0递归重命名一堆文件.目录结构如下所示:

Leaflets
+ HTML
  - File1
  - File2
  ...
+ HTMLICONS
  + IMAGES
    - Image1
    - Image2
  - File1
  - File2
  ...
+ RTF
  - File1
  - File2
  ...
+ SGML
  - File1
  - File2
  ...

我使用以下命令:

get-childitem Leaflets -recurse | rename -newname { $_.name.ToLower() }

它似乎重命名文件,但抱怨子目录:

Rename-Item : Source and destination path must be different.

我每月使用robocopy重新加载数据,但目录不会更改,因此我可以手动重命名.有没有办法get-children跳过子目录(比如find Leaflets -type f ...)？

谢谢.

更新:似乎问题是文件已经全部小写.我尝试将命令更改为:

get-childitem Leaflets -recurse | if ($_.name -ne $_name.ToLower()) rename -newname { …

我已经尝试使用这段代码并将其转换为我正在编写的用于编程语言处理的项目,但我遇到了一个简化版本的问题:

op = oneOf( '+ - / *')
lparen, rparen = Literal('('), Literal(')')

expr = Forward()
expr << ( Word(nums) | ( expr + op + expr ) | ( lparen + expr + rparen) )

我已经玩过这个简单设置的许多不同修改.通常,尝试以下方式:

print(expr.parseString('1+2'))

会回来['1'].虽然我陷入了深度递归中,例如:

print(expr.parseString('(1+2)'))

关于简单的递归而我无法解释的是我无法解析任意的算术表达式,例如1+(2 * 3-(4*(5+6)-(7))...？

我期待写一些递归下降解析器的伪代码.现在,我没有这种编码的经验.我在线阅读了一些例子,但它们只适用于使用数学表达式的语法.这是我基于解析器的语法.

S -> if E then S | if E then S else S | begin S L | print E

L -> end | ; S L

E -> i

我必须编写方法S(),L()并E()返回一些错误消息,但我在网上找到的教程没有帮助很多.任何人都可以指出我正确的方向并给我一些例子吗？

我想用C#或Java语法编写它,因为我更容易联系.

更新

public void S() {
    if (currentToken == "if") {
        getNextToken();
        E();

        if (currentToken == "then") {
            getNextToken();
            S();

            if (currentToken == "else") {
                getNextToken();
                S();
                Return;
            }
        } else {
            throw new IllegalTokenException("Procedure S() expected a 'then' token " + …

这已经在我脑海中浮现了一段时间.我对递归下降解析器很感兴趣,并且想知道如何实现它.我想要的是一个简单的解析器,它将理解简单的算术,如"5 + 5"或"(5 + 5)*3".

我认为第一步是编写一个'tokenizer',它获取整个输入字符串并将其分解为许多子字符串.这部分我已经完成了(我甚至不得不在这里询问.如果你不想,你不必关注链接,因为我也在这里发布了相关代码.)使用这个标记器我的,我结束了一个vector的stringS,或令牌.现在,困难的部分:我想解析那些令牌.

我已经阅读了关于递归下降解析器的维基百科文章.我确实理解整体概念,但一如既往,实施有点令人困惑.在那篇文章中,有一个非常简单的编程语言的递归下降解析器的C实现,也在本文中讨论过.我尽可能地研究了这段代码,并尝试基本上写同样的东西,但对于我的程序.以下是该代码.

我真正困惑的是这个解析器的作用.它似乎通过该程序并"期望"语法的某些部分.但一旦到达那里,它会做什么？例如,以下是维基百科代码中应该解析"术语"的一个函数:

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        getsym();
        factor();
    }
}

这是为了解析这个语法:

term = factor {("*"|"/") factor} .

这是有道理的.但它与实际用语有什么关系呢？假设这个术语只是"6",或者是"3*2"并且有价值6.如何将其纳入其余的输入？不应该term()返回一个double而不是void(返回6)？或者是以其他方式完成的？

另外,将这样的解析器输出到输出代码并立即对输入进行操作(即编译器与解释器)之间的区别是什么？这两个(至少在这个例子中)理论上是以相同的方式实现的,还是它们根本不同？

欢迎任何输入.这是我到目前为止的代码:

#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>
#include <sstream>

using namespace std;

vector<string> symbolize(string);
bool accept(string);
void getSymbol();
void error(string s);
bool expect(string);
void expression();
void term();
void …

我已经想出如何使用精神 - 也就是说,我写了一个中等复杂的语法.我总是采用增长程序的方法 - 一次一个子系统.我已经为复杂模型编写了数据结构,该模型在最高级别有4种类型.

我想使用由规则方法组成的语法一次解析一个类型的顶级类型 - 即,我想用一个顶级语法编​​写4个语法.如果这是可能的(我开始怀疑),有人可以发布片段或对这样做的项目的引用.

一个顶级语法具有50+(可能更多)规则(用于正确的错误处理)听起来不是很有趣(TMP代码易失/慢编译,并提供无用的错误消息).

我正在寻找手工编写递归下降解析器,我正在寻找有关如何构造它,算法等的良好资源.

我试图使用json.net解析json文件.该文件看起来像这样

{X:
   {
      Title:"foo",
      xxxx:xxxx
   }
}
{Y:
   {ZZ:
        {Title: "bar",...}
    }
}

我试图通过Title属性递归处理所有对象的结构.但我感到困惑JToken,JProperty,JContainer,JValue,JObject.阅读源代码并没有让我更加明智,也没有任何样本有帮助.我想要的东西是这样的

WalkNode(node, Action<Node> action)
{
    foreach(var child in node.Children)
    {
        Action(child);
        WalkNode(child);
    }
}

Parse()
{
   WalkNode(root, n=>
    {
        if(n["Title"] != null)
        {
           ...
        }
    });
}

我一直在尝试用变量创建我的解析器表达式,并将它们简化为二次表达式.

这是我的解析器语法:

Exercise : Expr '=' Expr
Expr : Term [+-] Expr | Term
Term : Factor [*/] Term | Factor
Factor: Atom [^] Factor | Atom
Atom: Number | Identified | [- sqrt] Atom | '(' Expr ')'

对于解析我正在使用递归下降解析器.我想说我想解析一下:

"2 - 1 + 1 = 0"

结果为0,解析器创建错误的树:

  -
 / \
2   +
   / \
  1   1

我怎样才能使这个语法保持联想？我是新手,请你告诉我哪里可以找到更多信息？我可以用递归下降解析器实现这一点吗？

根据维基百科上的"递归下降解析器",只有LL(k)语法才能实现没有回溯(也就是预测解析)的递归下降.

在其他地方,我已经读过Lua的实现使用这样的解析器.但是,该语言不是 LL(k).事实上,Lua天生就是含糊不清的:是a = f(g)(h)[i] = 1指a = f(g); (h)[i] = 1还是a = f; (g)(h)[i] = 1？这种歧义通过解析器中的贪婪来解决(因此上面被解析为错误的a = f(g)(h)[i]; = 1).

这个例子似乎表明预测解析器可以处理不是LL(k)的语法.事实上,它们是否能够处理LL(k)的超集？如果是这样,有没有办法找出一个给定的语法是否在这个超集中？

换句话说,如果我正在设计一种我想使用预测解析器解析的语言,我是否需要将语言限制为LL(k)？或者我可以适用更宽松的限制吗？