标签: parser-generator

我还没有进入计算机科学的正规语言领域,所以也许我的问题很愚蠢.我正在用C++编写一个简单的NMEA解析器,我必须选择:

我的第一个想法是手动构建一个简单的有限状态机,但后来我想也许我可以用更少的工作来做,甚至更有效率.我之前使用过正则表达式,但我认为NMEA正则表达式很长,应该花费很长时间来匹配它.

然后我考虑使用解析器生成器.我认为所有人都使用相同的方法:他们生成FSA.但我不知道哪个更有效率.你什么时候通常使用解析器生成器而不是正则表达式(我认为你可以在解析器生成器中编写正则表达式)？

请解释这些差异,我对理论和经验感兴趣.

我正在为PHP解析生成器.目前我正在尝试实现规范的LR(1)解析器,但它在后续语法上输出reduce-reduce冲突.这个语法不是LR(1)吗？或者我应该重新检查我的算法？

Bison中的语法(类似)表示法:

syntax : toplevels rules ;

toplevels
    : toplevel
    | toplevel toplevels
    ;

optsem : ';' | /* nothing */ ;

toplevel
    : 'grammar' backslash_separated_name optsem
    | 'option' options optsem
    | '@' period_separated_name '{' CODE '}' optsem
    ;

period_separated_name
    : ID '.' period_separated_name
    | ID
    ;

backslash_separated_name
    : ID '\\' backslash_separated_name
    | ID
    ;

options
    : single_option
    | '(' more_options ')'
    ;

more_options
    : single_option
    | single_option ';'
    | single_option ';' more_options
    ;

single_option
    : …

我试图使用Parsec来解析这样的事情:

property :: CharParser SomeObject
property = do
    name
    parameters
    value
    return SomeObjectInstance { fill in records here }

我正在实现iCalendar规范,并且每个类似都有一个名称:parameters:value triplet,非常类似于XML具有名称的方式:attributes:content triplet.事实上,您可以非常轻松地将iCalendar转换为XML格式(我不能真正看到它的优点).

我的观点是,参数根本不必按任何顺序排列,每个参数可能有不同的类型.一个参数可以是字符串,而另一个参数是另一个元素的数字id.它们可能没有任何相似性,最后,我想将它们正确地放在正确的记录字段中,以便我希望解析器返回的"SomeObjectInstance".我如何去做这类事情(或者你能指出一个例子,有人必须解析这样的数据)？

谢谢,我知道我的问题可能有点困惑,但这反映了我对我需要做的事情的理解程度.

编辑:我试图避免给出预期的输出(因为它很大,不是因为它是隐藏的)但这里是一个输入文件的例子(来自维基百科):

开始:VCALENDAR
版本:2.0
PRODID: - // hacksw/handcal // NONSGML v1.0 // EN开始
:VEVENT
UID:uid1@example.com
DTSTAMP:19970714T170000Z
ORGANIZER; CN = John Doe:MAILTO:john.doe@example .com
DTSTART:19970714T170000Z
DTEND:19970715T035959Z
摘要:巴士底日派对
END:VEVENT
END:VCALENDAR

正如您所看到的,它在VCalendar中包含一个VEvent,我在这里创建了代表它们的数据结构.

我正在尝试编写一个解析器来解析这种类型的文件到我的数据结构中,我被困在我需要处理任何类型的任何顺序的属性的位置; date,time,int,string,uid等.我希望在不重复整个iCalendar规范的情况下更有意义.

通过这篇关于Parser Combinators的信息性很好的文章阅读,我看到了这段代码:

class DisParser[+A](left: Parser[A], right: Parser[A]) extends Parser[A] {
  def apply(s: Stream[Character]) = left(s) match {
    case res: Success => res
    case _: Failure => right(s)
  }
}

当我尝试编译此代码时,我得到:

Parser.scala:19: error: class Success takes type parameters
    case res: Success => res
              ^
one error found

鉴于签名Parser:

case class Success[+A](value: A, rem: Stream[Character]) extends Result[A]

如何更改case res: Success => res线条以提供Success正确的类型参数？

我想将一些旧的手写解析代码转换为Boost Spirit,并在此过程中学习(更多)精神.旧代码使用流和模板来解析某些数据类型和某些容器的定义.

一些典型的格式:

VECTOR[number_of_items,(item_1, item_2 .... item_n)]
PAIR(p1, p2)
RECT[(left,top)-(right,bottom)]
Point( x, y )
Size( x, y )

解析函数是模板,其中项目的类型作为模板参数,并使用流作为输入,例如

 template<class T> std::istream& operator>>(std::Stream& in, std::vector<T>& v);

 template<class T1, class T2> std::istream& operator>>(std::istream& in, std::pair<T1, T2>& p);

 template<class T1, class T2> std::istream& operator>>(std::istream& in, RectType<T>& r);
 etc.

向量的解析器(流提取器)调用解析器以获取模板类型.

使用这些可以解析整数矩形,双矩形以及字符串和整数对的向量的定义.

是否有可能使用Spirit编写模板解析器来调用模板类型的子解析器？

我正在尝试学习Lemon解析器生成器的基础知识,但我很快就陷入了困境.

这是一个很小的语法:

%right PLUS_PLUS.
%left DOT.

program ::= expr.

member_expr ::= expr DOT IDENTIFIER.

lhs_expr ::= member_expr.

expr ::= lhs_expr.
expr ::= PLUS_PLUS lhs_expr.

它导致1个解析冲突:

State 3:
      (3) expr ::= lhs_expr *
      (4) expr ::= PLUS_PLUS lhs_expr *

                           DOT reduce       3      expr ::= lhs_expr
                           DOT reduce       4       ** Parsing conflict **
                     {default} reduce       4      expr ::= PLUS_PLUS lhs_expr

然而,如果我重写最后一条规则如下:

expr ::= PLUS_PLUS expr DOT IDENTIFIER.

然后它不会导致冲突.但我不认为这是正确的方法.

如果有人能解释什么是正确的方式,为什么,我会很感激.

我使用的第一个解析器生成器是Parse :: RecDescent,它可用的指南/教程很棒,但它最有用的特性是它的调试工具,特别是跟踪功能(通过将$ RD_TRACE设置为1来激活) ).我正在寻找一个解析器生成器,可以帮助您调试它的规则.

问题是,它必须用python或ruby编写,并且具有详细的模式/跟踪模式或非常有用的调试技术.

有谁知道这样的解析器生成器？

编辑:当我说调试时,我不是指调试python或ruby.我指的是调试解析器生成器,看看它在每一步中做了什么,看看它正在读取的每个字符,规则它正在尝试匹配.希望你明白这一点.

BOUNTY EDIT:为了赢得赏金,请展示一个解析器生成器框架,并说明它的一些调试功能.我再说一遍,我对pdb不感兴趣,但是在解析器的调试框架中.另外,请不要提及树梢.我对它不感兴趣.

你好伙伴堆栈流量成员.

我正在学习编译器类.我确实理解Top-Down Parser应该避免左递归,并转换为右递归方式.

问题是,

a)我理解正确的自上而下的解析器等于LL而自下而上的解析器等于LR？

b)我发现左递归是规则,自称为ex)Expr:== Expr'+'Term | 可能导致无限循环查找Expr的术语.但无论如何,在C或Java中考虑输入的任何示例代码？(我不想要解析器或扫描器代码)我需要的是具有句子形式的案例代码示例,它通过左递归发生无限循环.

c)在自上而下的解析器中使用右递归的方式实际上有什么不同？

ANS c)无需回溯.还有别的吗？

ANS b)x - 2 * y还有其他什么？因为这个用回溯方式解析.

我已经找到了非左递归和左递归的案例.

左递归语法

A -> Ax

非左递归语法

A -> Bx
B -> Ay

两者都进入无限循环.

谢谢你,感谢所有专家.

有时,为正则表达式搜索提供高度优化的函数会很方便,而不是在运行时包含生成解析器的库.是否有适合这种角色的解析器生成器？

理想情况下,它会:

• 创建一个C函数
• 生成与给定正则表达式对应的DFA
• 在简单的情况下,与KMP或Boyer-Moore一样高效

DRY ="不要重复自己".

我有一个基础css框架,我用它来构建更复杂的设计.最快的原型设计方法就是从最后开始并构建css以获得所需的结果(而不是从基本css编辑现有的css属性).

但是,在我完成之后,会有很多重复的类名和属性.

我正在寻找一个在线(或离线)工具,它将扫描我的css文件,并以删除冗余和重复的形式智能地重新制作它.

例如,如果这两行存在于CSS文件中:

//FROM THE BASE CSS
.header{
    font-weight:bold;
    font-size:1.5em;
    background:red;
    margin:0 auto;
    padding:20px
    }

//FROM THE ADDED CSS
.header{
    font-weight:normal;
    font-size:1.25em;
    background:blue;
    padding-bottom:0;
    margin-top:-20px
    }

所需的结果(给级联中的较低项目优先于前者)将删除.header指令的第一个实例,并将两个.header实例中的规则合并为一个.header指令,如下所示:

.header{
    font-weight:normal;
    font-size:1.25em;
    background:blue;
    margin:-20px auto 0 auto;
    padding:20px 20px 0 20px
    }

这样的应用程序是否存在？