Как вы могли бы реализовать вне-правила?

Question

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

Вкратце: Off-side rule означает в этом контексте, что отступ становится признанным синтаксическим элементом.

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

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 

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

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

Answer 1

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

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

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

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 для каждого столбца отступов и равное количество DEDENTs на обратном пути, если вы не будете искать пути, чтобы выяснить, где уровни отступа будут заканчиваться, и это не похоже на то, что вы хотите, чтобы токенизатор делал это. В этом случае я попробовал несколько разных вещей и просто сохранил счетчик в каждом токене NEWLINE, который дал изменение в отступе (положительном или отрицательном) для следующей логической строки. (Каждый токен также сохранял все конечные пробелы, в случае необходимости его сохранения; для NEWLINE хранимые пробелы включали сам EOL, любые промежуточные пустые строки и отступ в следующей логической строке.) Никаких отдельных токенов INDENT или DEDENT вообще. Получение парсера для решения этого было немного больше работы, чем просто вложение INDENT и DEDENTs, и, возможно, это был ад с сложной грамматикой, которая нуждалась в генераторе воображаемых парсеров, но это было не так плохо, как я боялся, или. Опять же, нет необходимости в синтаксическом анализаторе смотреть в NEWLINE, чтобы увидеть, есть ли в этой схеме INDENT.

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

Answer 2

Я недавно экспериментировал с этим, и я пришел к выводу, что для моих нужд по крайней мере, я хотел, чтобы 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() 

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

Answer 3

Tokenizer рубина для удовольствия:

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