Как бы вы пошли о реализации правила вне игры? - PullRequest
11 голосов
/ 24 октября 2008

Я уже написал генератор, который добивается цели, но я хотел бы знать, как лучше всего реализовать правило офсайда.

Коротко: Правило офсайда в этом контексте означает, что отступы распознаются как синтаксический элемент.

Вот правило офсайда в псевдокоде для создания токенизаторов, которые записывают отступ в удобной форме, я не хочу ограничивать ответы языком:

token NEWLINE
    matches r"\n\ *"
    increase line count
    pick up and store the indentation level
    remember to also record the current level of parenthesis

procedure layout tokens
    level = stack of indentation levels
    push 0 to level
    last_newline = none
    per each token
        if it is NEWLINE put it to last_newline and get next token
        if last_newline contains something
            extract new_level and parenthesis_count from last_newline
            - if newline was inside parentheses, do nothing
            - if new_level > level.top
                push new_level to level
                emit last_newline as INDENT token and clear last_newline
            - if new_level == level.top
                emit last_newline and clear last_newline
            - otherwise
                while new_level < level.top
                    pop from level
                    if new_level > level.top
                        freak out, indentation is broken.
                    emit last_newline as DEDENT token
                clear last_newline
        emit token
    while level.top != 0
        emit token as DEDENT token
        pop from level

comments are ignored before they are getting into the layouter
layouter lies between a lexer and a parser

Этот компоновщик не генерирует более одной NEWLINE одновременно и не генерирует NEWLINE при появлении отступа. Поэтому правила разбора остаются довольно простыми. Я думаю, это очень хорошо, но сообщите, есть ли лучший способ сделать это.

При использовании этого на некоторое время, я заметил, что после DEDENTs в любом случае было бы неплохо испускать новую строку, таким образом вы можете отделить выражения с помощью NEWLINE, сохраняя INDENT DEDENT как трейлер для выражения.

Ответы [ 3 ]

8 голосов
/ 03 ноября 2008

За последние пару лет я написал токенизаторы и парсеры для пары небольших ориентированных на индентирование доменных языков, и то, что у вас есть, выглядит для меня вполне разумным, чего бы это ни стоило. Если я не ошибаюсь, ваш метод очень похож на то, что делает, например, Python, который, похоже, должен иметь некоторый вес.

Преобразование NEWLINE NEWLINE INDENT в просто INDENT до того, как он попадет в парсер, определенно кажется правильным способом сделать что-то - это боль (IME) - всегда смотреть вперед в парсере! Я фактически сделал этот шаг как отдельный слой в том, что в итоге получилось трехэтапным: первый объединил то, что делают ваш лексер и Layouter, за вычетом всего, что было сделано в NEWLINE (что делало его очень простым), второй (тоже очень простой) ) слой сложил последовательные NEWLINEs и преобразовал NEWLINE INDENT в просто INDENT (или, собственно, COLON NEWLINE INDENT в INDENT, поскольку в этом случае все блоки с отступом всегда предшествовали двоеточиями), затем парсер был третьим этапом поверх этого. Но для меня также имеет смысл делать вещи так, как вы их описали, особенно если вы хотите отделить лексер от Layouter, что, вероятно, вы захотите сделать, если бы вы использовали инструмент генерации кода например, сделать свой лексер, как это принято.

У меня действительно было одно приложение, которое должно было быть немного более гибким в отношении правил отступов, по сути оставляя парсеру принудительное применение их при необходимости - в некоторых контекстах, например, должно быть допустимо следующее:

this line introduces an indented block of literal text:
    this line of the block is indented four spaces
  but this line is only indented two spaces

, который не очень хорошо работает с токенами INDENT / DEDENT, так как в итоге вам нужно сгенерировать один INDENT для каждого столбца отступа и равное количество DEDENT на обратном пути, если только вы не заглянете далеко вперед, чтобы выяснить, где Уровни отступа в конечном итоге окажутся такими, какими, по-видимому, вы не хотели бы, чтобы токенизатор делал. В этом случае я попробовал несколько разных вещей и в итоге просто сохранил счетчик в каждом токене NEWLINE, который дал изменение отступа (положительное или отрицательное) для следующей логической строки. (Каждый токен также сохранял все завершающие пробелы, на случай, если его нужно было сохранить; для NEWLINE сохраненный пробел включал сам EOL, любые промежуточные пустые строки и отступ в следующей логической строке.) Никаких отдельных токенов INDENT или DEDENT вообще нет. Заставить парсер справиться с этим было немного больше, чем просто вкладывать INDENTs и DEDENTs, и, возможно, это была бы адская сложная грамматика, для которой требовался причудливый генератор парсера, но это было не так плохо, как я опасался, или. Опять же, нет необходимости, чтобы парсер смотрел вперед от NEWLINE, чтобы увидеть, есть ли INDENT в этой схеме.

Тем не менее, я думаю, что вы согласитесь с тем, что разрешение и сохранение всевозможных сумасшедших пробелов в токенизаторе / Layouter и разрешение синтаксическому анализатору решать, что является литералом, а какой код - немного необычным требованием! Вы, конечно, не хотели бы, чтобы ваш синтаксический анализатор был обременен этим счетчиком отступов, если вы просто хотите иметь возможность, например, разбирать код Python. То, как вы делаете вещи, почти наверняка является правильным подходом для вашего приложения и многих других. Хотя, если у кого-то еще есть мысли о том, как лучше всего делать подобные вещи, я бы с удовольствием их услышал ...

3 голосов
/ 03 июня 2009

Я недавно экспериментировал с этим и пришел к выводу, что, по крайней мере, для своих нужд я хотел, чтобы NEWLINES отмечали конец каждого «оператора», независимо от того, был ли это последний оператор в блоке с отступом или нет то есть мне нужны переводы еще до DEDENT.

Мое решение состояло в том, чтобы перевернуть его с ног на голову, и вместо NEWLINES, отмечающего конец строк, я использую токен LINE, чтобы отметить начало строки.

У меня есть лексер, который сворачивает пустые строки (включая строки только для комментариев) и выдает один токен LINE с информацией об отступе последней строки. Затем моя функция предварительной обработки берет этот поток токенов и добавляет INDENT или DEDENT «между» любыми строками, где изменяется отступ. Так

line1
    line2
    line3
line4

даст поток токена

LINE "line1" INDENT LINE "line2" LINE "line3" DEDENT LINE "line4" EOF

Это позволяет мне писать четкие грамматические произведения для операторов, не беспокоясь об обнаружении конца операторов, даже если они заканчиваются вложенными, отступами, субблоками, что может быть сложно, если вместо этого вы используете NEWLINES (и DEDENTS). *

Вот ядро ​​препроцессора, написанное на O'Caml:

  match next_token () with
      LINE indentation ->
        if indentation > !current_indentation then
          (
            Stack.push !current_indentation indentation_stack;
            current_indentation := indentation;
            INDENT
          )
        else if indentation < !current_indentation then
          (
            let prev = Stack.pop indentation_stack in
              if indentation > prev then
                (
                  current_indentation := indentation;
                  BAD_DEDENT
                )
              else
                (
                  current_indentation := prev;
                  DEDENT
                )
          )
        else (* indentation = !current_indentation *)
          let  token = remove_next_token () in
            if next_token () = EOF then
              remove_next_token ()
            else
              token
    | _ ->
        remove_next_token ()

Я еще не добавил поддержку скобок, но это должно быть простое расширение. Тем не менее, он избегает появления паразитной строки в конце файла.

1 голос
/ 14 мая 2011

токенизатор в ruby ​​для развлечения:

def tokenize(input)
  result, prev_indent, curr_indent, line = [""], 0, 0, ""
  line_started = false

  input.each_char do |char|

    case char
    when ' '
      if line_started
        # Content already started, add it.
        line << char
      else
        # No content yet, just count.
        curr_indent += 1
      end
    when "\n"
      result.last << line + "\n"
      curr_indent, line = 0, ""
      line_started = false
    else
      # Check if we are at the first non-space character.
      unless line_started
        # Insert indent and dedent tokens if indentation changed.
        if prev_indent > curr_indent
          # 2 spaces dedentation
          ((prev_indent - curr_indent) / 2).times do
            result << :DEDENT
          end
          result << ""
        elsif prev_indent < curr_indent
          result << :INDENT
          result << ""
        end

        prev_indent = curr_indent
      end

      # Mark line as started and add char to line.
      line_started = true; line << char
    end

  end

  result
end

Работает только для двух пробелов. Результат что-то вроде ["Hello there from level 0\n", :INDENT, "This\nis level\ntwo\n", :DEDENT, "This is level0 again\n"].

...