标签: recursive-descent

下面简单的"计算器表达式"语法(BNF)可以使用一个简单的递归下降解析器轻松解析,这是一个预测LL(1):

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

因为总是足以看到下一个令牌以便知道要选择的规则.但是,假设我添加以下规则:

<command>   :=  <expr>
            |   <id> = <expr>

为了在命令行上与计算器交互,使用变量,如下所示:

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

我不能使用简单的LL(1)预测解析器来解析<command>规则吗？我试着为它编写解析器,但似乎我需要知道更多的令牌.是使用回溯的解决方案,还是我可以实现LL(2)并始终向前看两个令牌？

RD解析器生成器如何处理这个问题(例如ANTLR)？

是否可以在使用递归下降解析器检查数据是否与语法匹配的同时生成解析树？

如果是这样,当我递归下降时,我会用什么方法来构建树？

谢谢,Boda Cydo.

注意:我是解析新手.(已经问了几个关于SO的问题,我的情况越来越好了.)

我的计算机语言课已经过了几年,所以我忘记了BNF和EBNF的细节,而且我旁边没有教科书.具体来说,我忘记了如何将EBNF转换为BNF.

从我记忆中的一点点,我知道其中一个要点就是转换{ term }成<term> | <many-terms>.但我不记得其他规则.我试着在网上看一下,但是我只能找到关于家庭作业问题的链接,或者关于用花括号转换术语的小评论.我找不到定义翻译的详尽规则列表.

有人可以推荐一个在haskell上使用递归下降解析器的简单工作示例(代码)吗？我发现的所有信息都太难理解了.谢谢!

手写递归下降解析器(不可避免地是LL(k))在性能方面与生成的LALR解析器相比如何？

我知道LALR解析器能够处理比LL(k)更多的语法; 但是我打算手工编写我的解析器,递归下降似乎是最合适的选择.是否有可能手工编写任何其他类型(合理可读)？

NB我正在使用带尾调用优化(F#)的函数式语言,因此[精心定制的]递归不会像其他语言一样出现问题.

描述:

在阅读C book中的Compiler Design时,我遇到了以下规则来描述无上下文语法:

识别一个或多个语句列表的语法,每个语句都是一个后跟分号的算术表达式.语句由一系列以分号分隔的表达式组成,每个表达式包含一系列由星号(用于乘法)或加号(用于加法)分隔的数字.

这是语法:

1. statements ::= expression;
2.                | expression; statements
3. expression ::= expression + term
4.                | term
5. term       ::= term * factor
6.                | factor
7. factor     ::= number
8.                | (expression)

该书指出这种递归语法存在一个主要问题.几个产品的右侧出现在生产3的左侧(并且此属性称为左递归),并且某些解析器(如递归下降解析器)无法处理左递归生成.他们只是永远地循环.

您可以通过考虑解析器在替换具有多个右侧的非终端时如何决定应用特定生产来理解该问题.简单的情况在制作7和8中很明显.解析器可以通过查看下一个输入符号来选择在扩展因子时应用哪个制作.如果此符号是数字,则编译器应用Production 7并用数字替换该因子.如果下一个输入符号是一个左括号,则解析器将使用Production 8.但是,Productions 5和6之间的选择无法以这种方式解决.在生产6的情况下,术语的右侧以一个因子开始,该因子以数字或左括号开始.因此,解析器希望在替换术语时应用Production 6,并且下一个输入符号是数字或左括号.生产5-另一个右侧 - 以一个术语开始,该术语可以以一个因子开始,该因子可以以数字或左括号开头,这些是用于选择生产6的相同符号.

题:

书中的第二句话让我彻底迷失了.所以通过使用一些语句的例子(例如)5 + (7*4) + 14:

1. 因素和期限之间有什么区别？使用相同的例子
2. 为什么递归下降解析器不能处理左递归生成？(解释第二句).

给定一个字符串:

 var str1 = "25*5+5*7";

如果不使用evalJavaScript中的构造函数,我怎样才能编写一个名为"output"的函数,该函数接收字符串并输出字符串的算术值,在本例中为160？

我有一个导航表,使用ParentId连接回自己.我试图计算每条记录有多少后代,我知道我需要在递归中增加一个计数器,我只是不确定如何去做!

任何帮助将不胜感激!

CREATE TABLE [dbo].[Navigation](
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [AnchorText] [varchar](50) NOT NULL,
    [ParentID] [int] NULL)

insert into Navigation
select 'Level 1', null
union
select 'Level 2', 1
union
select 'Level 3', 2
union
select 'Level 4', 3


WITH NavigationCTE (Id, AnchorText, ParentId, NumberofDescendants) as
(
      Select Id, AnchorText, ParentId, 'Number of Descendants Here' as NumberofDescendants
      from dbo.Navigation nav

      union ALL 

      select nav.Id, nav.AnchorText, nav.ParentId,  'Number of Descendants Here' as NumberofDescendants
      from dbo.Navigation nav

      join Navigation ON nav.ParentId = …

我有一个复杂的Python数据结构(如果它很重要,它是一个很大的music21 Score对象),由于在对象结构内部某处存在弱化,它不会发痒.我以前用堆栈跟踪和python调试器调试过这样的问题,但总是很痛苦.是否有一个工具以递归方式对对象的所有属性运行dir(),查找隐藏在列表,元组,dicts等中的对象,并返回与特定值匹配的那些(lambda函数或类似的东西).一个很大的问题是递归引用,因此需要某种备忘录函数(如copy.deepcopy使用).我试过了:

import weakref
def findWeakRef(streamObj, memo=None):
    weakRefList = []
    if memo is None:
        memo = {}
    for x in dir(streamObj):
        xValue = getattr(streamObj, x)
        if id(xValue) in memo:
            continue
        else:
            memo[id(xValue)] = True
        if type(xValue) is weakref.ref:
            weakRefList.append(x, xValue, streamObj)
        if hasattr(xValue, "__iter__"):
            for i in xValue:
                if id(i) in memo:
                    pass
                else:
                    memo[id(i)] = True
                    weakRefList.extend(findWeakRef(i), memo)
        else:
            weakRefList.extend(findWeakRef(xValue), memo)
    return weakRefList

我大概可以继续在此堵孔(在ITER是不是我想要什么类型的字典,例如),但在此之前我把更多的时间到了,如果有人知道一个更简单的回答不知道.它可能是一个非常有用的通用工具.

我正在尝试学习解析表达式.我发现递归下降解析似乎很容易做到这一点.从维基百科,我在C中找到了一个例子.所以,我开始阅读和编辑这段代码,以了解它是如何工作的.我根据维基百科页面上的描述编写了缺失的例程,但它不能像我预期的那样在任何表达式中起作用.例如:1+2*3+1;return

error:语句:语法错误

有人可以解释我错过了什么吗？

目前的C代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {ident, number, lparen, rparen, 
          times, // symbol *
          slash, // symbol \ not added yet
          plus, // symbol +
          minus, //symbol -
          eql, //symbol ==
          neq, // !=
          lss, // <
          leq,// <=
          gtr, // >
          geq, // >= 
          callsym, // not added yet 
          beginsym, // not added yet 
          semicolon, // ;
          endsym, 
          ifsym, whilesym, becomes, thensym, dosym, constsym, 
          comma, //:
          varsym, procsym, period, oddsym, 
          not, …