Python 风格缩进的 PEG
https://stackoverflow.com/questions/4205442
-
25-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
你会怎样写一个 解析表达式语法 在以下任何解析器生成器中（聚乙二醇, 柑橘类, 树顶) 可以处理 Python/Haskell/CoffeScript 风格的缩进：
尚不存在的编程语言的示例：
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 => 3 } }
解决方案
纯 PEG 无法解析缩进。
但 钉住.js 能。
我做了一个快速而肮脏的实验（受到 Ira Baxter 关于作弊的评论的启发）并编写了一个简单的标记器。
对于更完整的解决方案（完整的解析器），请参阅这个问题： 使用 PEG.js 解析缩进级别
/* Initializations */
{
function start(first, tail) {
var done = [first[1]];
for (var i = 0; i < tail.length; i++) {
done = done.concat(tail[i][1][0])
done.push(tail[i][1][1]);
}
return done;
}
var depths = [0];
function indent(s) {
var depth = s.length;
if (depth == depths[0]) return [];
if (depth > depths[0]) {
depths.unshift(depth);
return ["INDENT"];
}
var dents = [];
while (depth < depths[0]) {
depths.shift();
dents.push("DEDENT");
}
if (depth != depths[0]) dents.push("BADDENT");
return dents;
}
}
/* The real grammar */
start = first:line tail:(newline line)* newline? { return start(first, tail) }
line = depth:indent s:text { return [depth, s] }
indent = s:" "* { return indent(s) }
text = c:[^\n]* { return c.join("") }
newline = "\n" {}
depths 是一堆缩进。indent() 返回一个缩进标记数组，start() 解包该数组以使解析器的行为有点像流。
钉住.js 生成文本：
alpha
beta
gamma
delta
epsilon
zeta
eta
theta
iota
这些结果：
[
"alpha",
"INDENT",
"beta",
"gamma",
"INDENT",
"delta",
"DEDENT",
"DEDENT",
"epsilon",
"INDENT",
"zeta",
"DEDENT",
"BADDENT",
"eta",
"theta",
"INDENT",
"iota",
"DEDENT",
"",
""
]
这个分词器甚至可以捕获错误的缩进。
其他提示
我认为像这样的缩进敏感语言是上下文敏感的。我相信 PEG 只能处理上下文无关的语言。
请注意，虽然 nalply 的答案肯定是正确的，即 PEG.js 可以通过外部状态（即可怕的全局变量）来做到这一点，但它可能是一条危险的道路（比全局变量的常见问题更糟糕）。某些规则最初可以匹配（然后运行其操作），但父规则可能会失败，从而导致操作运行无效。如果在此类操作中外部状态发生更改，您可能会得到无效状态。这太可怕了，可能会导致颤抖、呕吐和死亡。一些问题和解决方案在此处的评论中： https://github.com/dmajda/pegjs/issues/45
因此，我们在这里使用缩进真正做的是创建类似 C 风格块的东西，这些块通常有自己的词法范围。如果我正在为这样的语言编写编译器，我想我会尝试让词法分析器跟踪缩进。每次缩进增加时，它都可以插入一个“{”标记。同样，每次减少时，它都可以插入一个“}”标记。然后编写带有显式大括号的表达式语法来表示词法范围变得更加直接。
您可以在 Treetop 中使用语义谓词来执行此操作。在这种情况下，您需要一个语义谓词来检测由于出现具有相同或更少缩进的另一行而关闭空白缩进块。谓词必须计算从起始行开始的缩进，如果当前行的缩进已完成相同或更短的长度，则返回 true（块已关闭）。因为结束条件是依赖于上下文的，所以不能记住它。这是我要添加到 Treetop 文档中的示例代码。请注意，我已经重写了 Treetop 的 SyntaxNode 检查方法，以便更轻松地可视化结果。
grammar IndentedBlocks
rule top
# Initialise the indent stack with a sentinel:
&{|s| @indents = [-1] }
nested_blocks
{
def inspect
nested_blocks.inspect
end
}
end
rule nested_blocks
(
# Do not try to extract this semantic predicate into a new rule.
# It will be memo-ized incorrectly because @indents.last will change.
!{|s|
# Peek at the following indentation:
save = index; i = _nt_indentation; index = save
# We're closing if the indentation is less or the same as our enclosing block's:
closing = i.text_value.length <= @indents.last
}
block
)*
{
def inspect
elements.map{|e| e.block.inspect}*"\n"
end
}
end
rule block
indented_line # The block's opening line
&{|s| # Push the indent level to the stack
level = s[0].indentation.text_value.length
@indents << level
true
}
nested_blocks # Parse any nested blocks
&{|s| # Pop the indent stack
# Note that under no circumstances should "nested_blocks" fail, or the stack will be mis-aligned
@indents.pop
true
}
{
def inspect
indented_line.inspect +
(nested_blocks.elements.size > 0 ? (
"\n{\n" +
nested_blocks.elements.map { |content|
content.block.inspect+"\n"
}*'' +
"}"
)
: "")
end
}
end
rule indented_line
indentation text:((!"\n" .)*) "\n"
{
def inspect
text.text_value
end
}
end
rule indentation
' '*
end
end
这是一个小测试驱动程序，您可以轻松尝试：
require 'polyglot'
require 'treetop'
require 'indented_blocks'
parser = IndentedBlocksParser.new
input = <<END
def foo
here is some indented text
here it's further indented
and here the same
but here it's further again
and some more like that
before going back to here
down again
back twice
and start from the beginning again
with only a small block this time
END
parse_tree = parser.parse input
p parse_tree
我知道这是一个旧线程，但我只是想在答案中添加一些 PEGjs 代码。这段代码将解析一段文本并将其“嵌套”到一种“AST-ish”结构中。它只深入一层，看起来很丑，而且它并没有真正使用返回值来创建正确的结构，而是在内存中保留语法树，并在最后返回该树。这很可能变得笨拙并导致一些性能问题，但至少它做了它应该做的事情。
笔记：确保使用制表符而不是空格！
{
var indentStack = [],
rootScope = {
value: "PROGRAM",
values: [],
scopes: []
};
function addToRootScope(text) {
// Here we wiggle with the form and append the new
// scope to the rootScope.
if (!text) return;
if (indentStack.length === 0) {
rootScope.scopes.unshift({
text: text,
statements: []
});
}
else {
rootScope.scopes[0].statements.push(text);
}
}
}
/* Add some grammar */
start
= lines: (line EOL+)*
{
return rootScope;
}
line
= line: (samedent t:text { addToRootScope(t); }) &EOL
/ line: (indent t:text { addToRootScope(t); }) &EOL
/ line: (dedent t:text { addToRootScope(t); }) &EOL
/ line: [ \t]* &EOL
/ EOF
samedent
= i:[\t]* &{ return i.length === indentStack.length; }
{
console.log("s:", i.length, " level:", indentStack.length);
}
indent
= i:[\t]+ &{ return i.length > indentStack.length; }
{
indentStack.push("");
console.log("i:", i.length, " level:", indentStack.length);
}
dedent
= i:[\t]* &{ return i.length < indentStack.length; }
{
for (var j = 0; j < i.length + 1; j++) {
indentStack.pop();
}
console.log("d:", i.length + 1, " level:", indentStack.length);
}
text
= numbers: number+ { return numbers.join(""); }
/ txt: character+ { return txt.join(""); }
number
= $[0-9]
character
= $[ a-zA-Z->+]
__
= [ ]+
_
= [ ]*
EOF
= !.
EOL
= "\r\n"
/ "\n"
/ "\r"
