Jak byś poszła na temat wdrażania zasad zewnętrznych?

Question

Napisałem już generator, który rozwiązuje problem, ale chciałbym poznać najlepszy możliwy sposób implementacji reguły off-side.

Krótko: Off-side rule oznacza w tym kontekście, że wcięcie zostaje rozpoznane jako element syntaktyczny.

Oto przepis na spalonym Pseudokod dokonywania tokenizers przechwytującej wcięcie w postaci użytkowej, nie chcę, aby ograniczyć odpowiedzi poprzez język:

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 

Ten Layouter nie generuje więcej niż jeden na NEWLINE czas i nie generuje NEWLINE, gdy pojawi się wcięcie. Dlatego też reguły analizy składniowej są dość proste. Myślę, że jest całkiem niezły, ale poinformuj, czy jest lepszy sposób na osiągnięcie tego.

Podczas korzystania z tego przez chwilę zauważyłem, że po DEDENTACH może i tak być fajnie emitować newline, w ten sposób można oddzielić wyrażenia za pomocą NEWLINE, jednocześnie zachowując INDENT DEDENT jako zwiastun dla wyrażenia.

Answer 1

Napisałem tokenizery i parsery dla kilku małych języków zorientowanych na wcięcia w domenie w ciągu ostatnich kilku lat, a to, co tam masz, wydaje mi się całkiem rozsądne, niezależnie od tego, co jest warte. Jeśli się nie mylę, twoja metoda jest dość podobna do tego, co robi Python, na przykład, wydaje się, że powinna mieć jakąś wagę.

Konwersja NEWLINE NEWLINE INDENT na samo TRAWE zanim trafi do parsera zdecydowanie wydaje się być właściwym sposobem robienia rzeczy - to ból (IME), aby zawsze być przedewszystkiem szukającym tego w parserze! Tak naprawdę zrobiłem ten krok jako osobną warstwę, co ostatecznie było procesem trzystopniowym: pierwszy zestawił to, co twój lexer i layouter robił z pominięciem wszystkiego, co NEWLINE z wyprzedzeniem (co uczyniło to bardzo prostym), drugi (również bardzo prosty) warstwa złożona z kolejnych NEWLINE'ów i skonwertowana NEWLINE TRAWA na właśnie TRAWĘ (lub, właściwie, KOLEJNA NEWLINE ZNACZY do TŁUSZCZU, ponieważ w tym przypadku wszystkie wcięte bloki były zawsze poprzedzone dwukropkami), a następnie parser był trzecim etapem. Ale mam także dużo sensu robić rzeczy tak, jak je opisałeś, zwłaszcza jeśli chcesz oddzielić lexer od layoutera, co prawdopodobnie chciałbyś zrobić, gdybyś używał narzędzia do generowania kodu na przykład, aby twój lexer był powszechną praktyką.

miałem jeden wniosek, że potrzebne będzie nieco bardziej elastyczny o reguł wcięć, zasadniczo pozostawiając parser egzekwować je, gdy są potrzebne - dodaje się musiała być ważna w pewnych kontekstach, na przykład:

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 

który nie działa bardzo dobrze z tokenami INDENT/DEDENT, ponieważ w końcu będziesz musiał wygenerować jeden INDENT za każdą kolumnę wcięcia i taką samą liczbę DEDENTÓW w drodze powrotnej, chyba że spojrzysz w przyszłość, aby dowiedzieć się, gdzie poziomy wcięcia będą w końcu istniały, co nie wygląda na to, że chcesz zrobić tokenizera. W tym przypadku próbowałem kilku różnych rzeczy i skończyło się właśnie przechowywaniem licznika w każdym tokenie NEWLINE, który dał zmianę wcięcia (dodatnią lub ujemną) dla następującej linii logicznej. (Każdy token również zapisywał wszystkie końcowe spacje, na wypadek, gdyby wymagało zachowania, dla NEWLINE zapisana biała spacja zawierała sam EOL, wszelkie interweniujące puste wiersze i wcięcie w następującej linii logicznej.) Brak oddzielnych tokenów INDENT lub DEDENT. Załatwienie parsera wymagało trochę więcej pracy niż tylko zagnieżdżanie INDENTÓW i DEDENTÓW, i mogło być piekłem ze skomplikowaną gramatyką, która wymagała generatora parsera, ale nie było tak źle, jak się obawiałem, zarówno. Ponownie, nie ma potrzeby, aby analizator składniowy patrzył w przód z NEWLINE, aby sprawdzić, czy w tym schemacie pojawi się INDENT.

Nadal myślę, że zgodzicie się na to, że pozwolicie i zachowacie wszystkie wariacje w tokenizerze/layouteru i pozwalacie parserowi decydować, co jest dosłowne, a kod jest nieco niezwykłym wymogiem! Z pewnością nie chciałbyś, aby twój parser został osiodłany tym licznikiem wcięć, gdybyś tylko chciał móc sparsować kod Pythona, na przykład. Sposób, w jaki robisz różne rzeczy, jest prawie na pewno właściwym podejściem do twojej aplikacji i wielu innych. Chociaż, jeśli ktokolwiek myśli o tym, jak najlepiej robić tego typu rzeczy, to oczywiście z przyjemnością je usłyszę ...

Answer 2

Eksperymentowałem z tym ostatnim i doszedłem do wniosku, że dla moich potrzeb przynajmniej chciałem, aby NEWLINES zaznaczyły koniec każdego "oświadczenia", niezależnie od tego, czy było to ostatnie zdanie w wciętym bloku, czy nie, tj. potrzebuję nowych znaków jeszcze przed DEDENTEM.

Moim rozwiązaniem było obrócenie go na głowie, a zamiast NEWLINES oznaczających koniec linii używam tokena LINE do oznaczenia początku linii.

Mam lexer, który zwija puste linie (w tym linie tylko komentarz) i emituje pojedynczy token LINE z informacją o wcięciu ostatniej linii. Następnie moja funkcja preprocesingu bierze ten strumień tokenów i dodaje INDENT lub DEDENT "pomiędzy" dowolnymi liniami, w których zmienia się wcięcie. Więc

line1 
    line2 
    line3 
line4 

dałoby tokena strumień

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

To pozwala mi pisać jasne produkcje gramatyki wypowiedzi bez obawy o wykryciu końca oświadczeń nawet wtedy, gdy kończą się zagnieżdżone wcięte, podbloków, coś może to być trudne, jeśli pasujesz do NEWLINES (i DEDENTS).

Oto rdzeń preprocesora, napisany w 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() 

Nie dodano wsparcie dla jeszcze nawiasach, ale to powinno być proste rozszerzenie. Pozwala to jednak uniknąć wysyłania bezpańskiej LINII na końcu pliku.

Answer 3

Tokenizer w Ruby dla zabawy:

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 

Czy tylko pracę za dwa-space-wcięcia. Wynik jest podobny do ["Hello there from level 0\n", :INDENT, "This\nis level\ntwo\n", :DEDENT, "This is level0 again\n"].