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

Question

Как бы вы написали грамматику выражения синтаксического анализа в любом из следующих генераторов синтаксического анализатора ( PEG.js , Цитрус , 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

PEG не может разобрать отступ.

Но 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",
   "",
   ""
]

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

Answer 2

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

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

Answer 3

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

Answer 4

Вы можете сделать это в Treetop, используя семантические предикаты. В этом случае вам нужен семантический предикат, который обнаруживает закрытие блока с пробелами с отступом из-за появления другой строки с таким же или меньшим отступом. Предикат должен считать отступ от начальной строки и возвращать значение true (блок закрыт), если отступ текущей строки закончился на той же или меньшей длине. Поскольку условие закрытия зависит от контекста, оно не должно быть запомнено. Вот пример кода, который я собираюсь добавить в документацию Treetop. Обратите внимание, что я переопределил метод проверки синтаксиса 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"