PEG爲Python風格縮進

Question

你怎麼會寫在以下任何解析器生成的Parsing Expression Grammar（PEG.js，Citrus，Treetop），它可以處理的Python /哈斯克爾/ CoffeScript風格縮進：

一個不yet-的例子現有編程語言：

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 } } 

Answer 1

Pure PEG無法解析縮進。

但是peg.js可以。

我做了一個快速而骯髒的實驗（受到Ira Baxter關於作弊的評論的啓發）。

/* 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（）解開數組，使分析器的行爲有點像流。

peg.js產生的文本：

alpha 
    beta 
    gamma 
    delta 
epsilon 
    zeta 
    eta 
theta 
    iota 

這些結果：

​​

這個解析器甚至捕捉壞縮進。

Answer 2

我認爲這樣的縮進敏感語言是上下文敏感的。我相信PEG只能做上下文無關的語言。

請注意，儘管nalply的回答當然是正確的，但PEG.js可以通過外部狀態（即可怕的全局變量）做到這一點，但它可能是一個危險的走下路徑（比全局變量的常見問題更糟糕） 。一些規則最初可以匹配（然後運行其操作），但父規則可能會失敗，從而導致操作無效。如果外部狀態在這樣的動作中被改變，則可能以無效狀態結束。這是非常糟糕的，並可能導致震顫，嘔吐和死亡。這裏有一些問題和解決方案在這裏的評論：https://github.com/dmajda/pegjs/issues/45

Answer 3

所以我們真正在這裏做的縮進創建類似於C樣式塊，往往有自己的詞彙範圍。如果我爲這樣的語言編寫編譯器，我想我會嘗試讓詞法分析器跟蹤縮進。每次縮進都可以插入一個'{'標記。同樣每次它減少它可能會嵌入一個'}'令牌。然後用明確的大括號來表達詞法範圍來編寫表達式語法變得更直接。

Answer 4

您可以使用語義謂詞在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 

Answer 5

我知道這是一個古老的線程，但我只是想一些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"