代码之家 › 专栏 › 技术社区 › Vlad Gudim nuriaion

递归下降分析器ll(1)数据类型的良好语法

recursive-descent expressionengine dsl grammar parsing

1

Vlad Gudim nuriaion · 技术社区 · 15 年前

我正在为生产环境构建一个自定义表达式解析器和求值器,以向用户提供有限的dsl。解析器本身作为dsl,需要简单一些。解析器将用一种不支持动态表达式解析的外来语言构建,也没有任何解析器生成器工具可用。

我现在的决定是使用ll(1)语法的递归下降方法,这样即使是以前没有计算表达式经验的程序员也可以快速学习代码的工作原理。

它必须处理由几种数据类型组成的混合表达式:小数、百分比、字符串和日期。而dd/mm/yyyy格式的日期很容易与一系列分区操作混淆。

哪里是解决这个问题的好办法?

我自己的解决方案旨在保持解析器的简单性,包括在日期前面加上一个特殊的符号,比如撇号:

<date>   ::= <apostr><digit><digit>/<digit><digit>/<digit><digit><digit><digit>

<apostr> ::= '

<digit>  ::= '0'..'9'

3 回复 | 直到 15 年前

1

2

T.E.D. 15 年前

首先,我是ll解析器的粉丝,所以我非常赞同您的方法。注意,最新流行的解析器生成器之一( ANTLR 是LL。如果您允许更多的前瞻性,而不是将自己限制在ll(1)上,那么您可以使用lr(1)解析器做任何您想做的事情,但是代码将更加清晰、可靠和易于调试。

我对你的整体语法不太了解。您可能能够设计一些东西,以便ll解析器始终能够从上下文中判断它是整数表达式还是日期常量。但是,假设你不能,是的,你需要某种方法来区分。我唯一能想到的是用反斜杠代替斜杠作为分隔符,但这有点难看。

2

SK-logic 15 年前

您需要的是一个具有无限前瞻性的类似ll的无词汇解析器。也就是说,它是peg。

http://en.wikipedia.org/wiki/Parsing_expression_grammar

有了有序的选择,就很容易避免这种日期与常量文字划分的混淆。

3

0

mjv 15 年前

当一种语言是为人类输入的时候,定义它同样是一个问题

添加语法约束以确保清晰且易于解析
删除/弯曲语法,以确保语言对预期的人类受众来说是直观的、自然的。

满足第二个需求比第一个要困难得多,需要深入了解

语言的预期用例
哪种键盘/输入设备可用?在允许的字符中是否有一些字符难以产生或在显示器上难以看到?
哪些标记/表达式将被频繁使用,哪些只是偶尔需要? 用户是否经常输入简短的、特别的代码片段,或者程序是否打算在长时间内重用和修改?
…等。
目标受众的背景/文化
如果可能的话,哪些来自其他常规(和纯自然)语言的通用实践/习惯用法可以或应该重用?
一个人应该喜欢简洁但隐晦的风格,还是更明确但更冗长的风格?
…等.

基本上,如果不能很好地掌握预期的用法和用户,就很难对语言语法提出建议。
不过,对于日期格式问题,我建议如下:

对日期值使用其他格式 ;对于用户来说是“自然”的,但对于普通语法来说却足够独特。
例如,使用 3个字母的缩写 (下行DSL与英语或其他语言联系在一起,但也有优势,人类对哪一天哪一个月的模棱两可被消除了)。试探性地:

  dd-mmm-yyyy    (may seem unnatural in cultures where the prevailing date order 
                  starts with the month maybe yyyy-mmm-dd then ?)
  mmm-dd-yyyy    (better for the above mentioned cultures)
  ddmmmyyyy      (avoid the dashes, but impose leading zeros)

  MnnDnnYyyyy    (using "M", "D" and "Y" (or others) as explicit prefixes; now, 
                  this is completely culture neutral, but maybe a bit awkward...)

不管怎样,只是想法…适用性将因提及的人类/文化因素而异, 和其他的语法。例如,上面的内容可能意味着要显式地标记变量(这是许多语言使用$前缀的原因之一),以避免可能与[奇数,但可能的]变量标识符冲突。

简言之,其思想是通过使12个月标记对解析器来说是一个足够好的鉴别器来代替对特殊字符前缀的需要(这可能会与使用这些字符进行数学和其他表达式相冲突)。