标签: peg

从这个维基百科页面:

无上下文语法和解析表达式语法之间的根本区别在于PEG的选择运算符是有序的.如果第一个替代方案成功,则忽略第二个替代方案.因此,有序选择不是可交换的,不像无上下文选择,如无上下文语法和正则表达式.有序选择类似于某些逻辑编程语言中可用的软切算子.

为什么PEG的选择算子会使匹配短路？是因为最小化内存使用量(由于记忆)？

我不确定正则表达式中的选择运算符是什么,但我们假设它是:/[aeiou]/匹配元音.所以这个正则表达式是可交换的,因为我可以用5个中的任何一个来编写它!元音字符的(五个阶乘)排列？即/[aeiou]/行为相同/[eiaou]/.它是可交换的有什么好处？(参见PEG的非交换性)

结果是,如果CFG直接音译为PEG,则通过从可能的解析中确定性地选择一个解析树来解决前者中的任何歧义.通过仔细选择指定语法备选的顺序,程序员可以很好地控制选择哪个解析树.

这说PEG的语法优于CFG吗？

您将如何在以下任何可以处理Python/Haskell/CoffeScript样式缩进的分析器生成器(PEG.js,Citrus,Treetop)中编写解析表达式语法:

尚未存在的编程语言的示例:

square x =
    x * x

cube x =
    x * square x

fib n =
  if n <= 1
    0
  else
    fib(n - 2) + fib(n - 1) # some cheating allowed here with brackets

更新: 不要尝试为上面的示例编写解释器.我只对缩进问题感兴趣.另一个例子可能是解析以下内容:

foo
  bar = 1
  baz = 2
tap
  zap = 3

# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => …

我试图通过在PEG.js操场上输入简单的语法来绕过PEG .

例1:

• 输入: "abcdef1234567ghijklmn8901opqrs"

• 期望的输出: ["abcdef", "1234567", "ghijklmn", "8901", "opqrs"]

• 实际产量: ["abcdef", ["1234567", ["ghijklmn", ["8901", ["opqrs", ""]]]]]

这个例子非常有效,但是我可以让PEG.js不将生成的数组嵌套到百万级别吗？我假设诀窍是使用concat()而不是join()某个地方,但我找不到这个地方.

start
  = Text

Text
  = Numbers Text
  / Characters Text
  / EOF

Numbers
  = numbers: [0-9]+ {return numbers.join("")}

Characters
  = text: [a-z]+ {return text.join("")}

EOF
  = !.

例2:

与示例1相同的问题和代码,但将字符规则更改为以下内容,我预期会产生相同的结果.

Characters
  = text: (!Numbers .)+ {return text.join("")}

结果输出是:

[",a,b,c,d,e,f", ["1234567", [",g,h,i,j,k,l,m,n", ["8901", [",o,p,q,r,s", ""]]]]]

为什么我得到所有这些空的比赛？

例3:

最后一个问题.这根本不起作用.我怎样才能使它工作？对于奖励积分,任何关于效率的指针？例如,如果可能,我应该避免递归吗？

我也很欣赏一个很好的PEG教程的链接.我已阅读(http://www.codeproject.com/KB/recipes/grammar_support_1.aspx),但正如您所见,我需要更多帮助......

• 输入: 'abcdefghijklmnop"qrstuvwxyz"abcdefg'
• 期望的输出: ["abcdefghijklmnop", "qrstuvwxyz", "abcdefg"] …

我想用我的语法忽略空格和新行,因此它们在PEG.js输出中缺失.此外,括号内的文字应该在新数组中返回.

语法

start
  = 'a'? sep+ ('cat'/'dog') sep* '(' sep* stmt_list sep* ')'

stmt_list
  = exp: [a-zA-Z]+ { return new Array(exp.join('')) }

sep
  = [' '\t\r\n]

测试用例

a dog( Harry )

产量

[
   "a",
   [
      " "
   ],
   "dog",
   [],
   "(",
   [
      " "
   ],
   [
       "Harry"
   ],
   [
      " "
   ],
   ")"
]

我想要的输出

[
   "a",
   "dog",
   [
      "Harry"
   ]
]

有没有一种工具可以将PEG.js语法翻译成TextMate语法？

我正在构建自己的语言,并希望在我的首选编辑器TextMate中使用语法高亮显示.我语言的语法是用PEG.js构建的.根据此用例的 TextMate文档,我必须以与PEG.js不兼容的形式编写TextMate语法.

我开始编写一个新的TextMate语法,但我很快注意到翻译整个语法需要很长时间,甚至是与可接受的语法高亮相关的子集.由于我非常懒惰而且不想做所有这些繁琐的工作,我想到了自动完成这项任务.

谁能给我任何线索如何自动化,或者至少加速从PEG.js语法生成TextMate语法？

我很享受YARD的使用:

http://www.ootl.org/yard/

http://code.google.com/p/yardparser/

http://www.codeproject.com/KB/recipes/yard-tokenizer.aspx

我能够构建全功能计算器.我正在评估YARD做PHP解析器.请关注PEG语法和解析器生成器的局限性.非常感谢你!

我一直试图找出我设计的语言的基本骨架,并且我正在尝试使用Parsimonious来为我解析.截至目前,我已经宣布了以下语法:

grammar = Grammar(
    """
    program = expr*
    expr    = _ "{" lvalue (rvalue / expr)* "}" _
    lvalue  = _ ~"[a-z0-9\\-]+" _
    rvalue  = _ ~".+" _
    _       = ~"[\\n\\s]*"
    """
)

当我尝试输出简单输入字符串的结果AST时"{ do-something some-argument }":

print(grammar.parse("{ do-something some-argument }"))

Run Code Online (Sandbox Code Playgroud)

Parsimonious决定拒绝它,然后给我这个有点神秘的错误:

Traceback (most recent call last):
  File "tests.py", line 13, in <module>
    print(grammar.parse("{ do-something some-argument }"))
  File "/usr/local/lib/python2.7/dist-packages/parsimonious/grammar.py", line 112, in parse
    return self.default_rule.parse(text, pos=pos)
  File "/usr/local/lib/python2.7/dist-packages/parsimonious/expressions.py", line 109, in parse
    raise IncompleteParseError(text, …

Run Code Online (Sandbox Code Playgroud)

我想知道是否可以直接使用CFG或PEG语法作为代码完成的基础而无需修改.我听说IDE中的代码完成有时会被操纵和按摩,甚至是硬编码,因此它的性能更好.

我想在一个小型DSL上完成代码编写,所以我完全理解一个语法不能帮助一个具有库函数等知识的代码完成系统.

据我所知,解析器本身至少需要提供一个系统来查询接下来的内容.

特别是我对使用peg.js 或jison的javascript代码完成解决方案感兴趣

我已经看到一些声称优化的PEG解析器通常不会比优化的LALR(1)或LL(k)解析器更快.(当然,解析的性能取决于特定的语法.)

我想知道PEG解析器是否存在任何特定限制,无论是一般有效还是PEG语法的某些子集都会使它们在性能方面低于LALR(1)或LL(k).

特别是,我对解析器生成器很感兴趣,但是假设在任何特定情况下都可以调整它们的输出以提高性能.我还假设解析器已经过优化,如果需要提高性能,可以稍微调整一下特定的语法.

我在玩PEG.js

start = keyword

keyword = a:[a-z]? {return a.join("");}

为什么我会在这里出现错误：

a.join 不是函数

当我输入一个有效的字符串时abc？