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

Как вы напишете грамматику выражения Parsing в любом из следующих генераторов Parser (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

Update: Не пытайтесь написать интерпретатор для приведенных выше примеров. Меня интересует проблема с отступом. Другим примером может быть синтаксический анализ следующего:

foo
  bar = 1
  baz = 2
tap
  zap = 3

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

Ответ 1

Чистый ПЭГ не может разобрать отступ.

Но peg.js может.

Я провел быстрый и грязный эксперимент (вдохновленный комментарием Айры Бакстер о мошенничестве) и написал простой токенизатор.

Для более полного решения (полный синтаксический анализатор), пожалуйста, смотрите этот вопрос: Разобрать уровень отступа с 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",
   "",
   ""
]

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

Ответ 2

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

Обратите внимание, что, хотя краткий ответ, безусловно, верен, PEG.js может делать это через внешнее состояние (т.е. страшные глобальные переменные), но это может быть опасным путем (хуже, чем обычные проблемы с глобальными переменными). Некоторые правила могут изначально совпадать (а затем запускать свои действия), но родительские правила могут не работать, в результате чего выполнение действия становится недействительным. Если внешнее состояние изменяется в таком действии, вы можете получить недопустимое состояние. Это очень ужасно, и может привести к тремору, рвоте и смерти. Некоторые проблемы и решения этого в комментариях здесь: https://github.com/dmajda/pegjs/issues/45

Ответ 3

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

Ответ 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 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 further indented
    and here the same
      but here it 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

Ответ 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"