PEG для Python стиль отступов

Question

Как бы вы написать в любой из следующих генераторов Parser в Parsing Expression Grammar (PEG.js, Citrus, Treetop), который может работать с 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 } } 

Answer 1

Pure PEG не может анализировать отступы.

Но 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() разворачивает массив, чтобы заставить парсер вести себя как поток.

peg.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", 
    "", 
    "" 
] 

Этот анализатор даже ловит плохих отступы.

Answer 2

Я думаю, что такой чувствительный к отступлению язык является контекстно-зависимым. Я считаю, что PEG может делать только контекстно-свободные langauges.

Обратите внимание, что, хотя ответ nalply, безусловно, правильный, что PEG.js может сделать это через внешнее состояние (т. Е. Ужасные глобальные переменные), это может быть опасный путь для ходьбы (хуже обычных проблем с глобальными переменными) , Некоторые правила могут первоначально совпадать (и затем запускать их действия), но правила родителя могут завершиться неудачно, что приведет к недействительности действия. Если в таком действии изменяется внешнее состояние, вы можете получить недопустимое состояние. Это очень ужасно и может привести к треморам, рвоте и смерти. Некоторые вопросы и решения в этом приведены здесь:

Answer 3

Так что мы действительно делаем здесь с отступом, создаем что-то вроде блоков C-стиля, которые часто имеют свою лексическую область. Если бы я писал компилятор для такого языка, я бы попробовал, и lexer отслеживал отступ. Каждый раз, когда увеличивается отступ, он может вставить маркер '{'. Аналогично каждый раз, когда он уменьшается, он может вставлять токен. Тогда запись грамматики выражения с явными фигурными фигурными скобками для представления лексической области становится более прямой.

Answer 4

Вы можете сделать это в Treetop с помощью семантических предикатов.В этом случае вам нужен семантический предикат, который обнаруживает закрытие блока с отступом белого пространства из-за появления другой строки с таким же или меньшим отступом. Предикат должен считать отступ от строки открытия и возвращать true (блокировать), если отступ текущей строки заканчивается на той же или более короткой длине. Поскольку условие закрытия зависит от контекста, оно не должно запоминаться. Вот пример кода, который я собираюсь добавить в документацию Treetop. Обратите внимание, что я переопределил метод проверки SyntaxNode Treetop, чтобы упростить визуализацию результата.

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"