Jak napisać interpreter / parser poleceń?


22

Problem: uruchamiaj polecenia w postaci łańcucha.

  • przykład polecenia:

    /user/files/ list all; równoważny: /user/files/ ls -la;

  • inny:

    post tw fb "HOW DO YOU STOP THE TICKLE MONSTER?;"

równoważny: post -tf "HOW DO YOU STOP THE TICKLE MONSTER?;"

Aktualne rozwiązanie:

tokenize string(string, array);

switch(first item in array) {
    case "command":
        if ( argument1 > stuff) {
           // do the actual work;
        }
}

Problemy, które widzę w tym rozwiązaniu to:

  • Brak sprawdzania błędów oprócz zagnieżdżonego ifs-else w każdym przypadku. Skrypt staje się bardzo duży i trudny do utrzymania.
  • Polecenia i odpowiedzi są zakodowane na stałe.
  • Nie ma możliwości sprawdzenia, czy flagi są poprawne, czy brakuje parametrów.
  • Brak inteligencji sugerującej, że „możesz chcieć uruchomić $ command”.

Ostatnią rzeczą, której nie mogę rozwiązać, są synonimy w różnych kodowaniach, na przykład:

case command:
case command_in_hebrew:
    do stuff;
break;

Ten ostatni może być trywialny, ale cóż, chcę zobaczyć solidne fundusze tego rodzaju programu.

Obecnie programuję to w PHP, ale mogę to zrobić w Perlu.


W ogóle nie rozumiem, w jaki sposób odnosi się to konkretnie do PHP. W tym temacie interpretera / kompilatora jest już wiele wątków na temat SO i SE.
Raffael

3
Nikt nie wspominał o getopt?
Anton Barkovsky

@AntonBarkovsky: Tak. Zobacz moje linki. Myślę, że odpowiedzi takie jak Ubermensch są po prostu zbyt skomplikowane w stosunku do tego, co OP próbuje zrobić.
quentin-starin

1
Przytoczyłem również proste podejście przy użyciu RegExp. Odpowiedź jest również zaktualizowana
Ubermensch,

Nie wspomniał o żadnym konkretnym programie. język możesz dodać tag „c”, tag „ruby”, tag „php”, być może istnieje biblioteka typu open source, biblioteka standardowa lub „powszechnie używana, jeszcze nie standardowa biblioteka”. za twój progr. język
umlcat,

Odpowiedzi:


14

Przyznaję szczerze, budowanie parsera jest żmudnym zajęciem i zbliża się do technologii kompilatora, ale zbudowanie takiej okazałoby się dobrą przygodą. A parser pochodzi z tłumaczem. Więc musisz zbudować oba.

Szybkie wprowadzenie do parsera i tłumaczy

To nie jest zbyt techniczne. Więc eksperci się nie denerwują.

Po wprowadzeniu niektórych danych wejściowych do terminala, terminal dzieli dane wejściowe na wiele jednostek. Wejście nazywa się wyrażeniem, a wiele jednostek nazywa się tokenami. Te tokeny mogą być operatorami lub symbolami. Więc jeśli wpiszesz 4 + 5 w kalkulatorze, to wyrażenie zostanie podzielone na trzy tokeny 4, +, 5. Plus jest uważany za operatora, podczas gdy 4 i 5 symboli. Jest to przekazywane do programu (traktuj to jako tłumacz), który zawiera definicję operatorów. Na podstawie definicji (w naszym przypadku dodaj), dodaje dwa symbole i zwraca wynik do terminala. Wszystkie kompilatory są oparte na tej technologii. Program, który dzieli wyrażenie na wiele tokenów, nazywa się lexer, a program, który konwertuje te tokeny na tagi do dalszego przetwarzania i wykonywania, nazywa się parserem.

Lex i Yacc to kanoniczne formy do budowania leksyk i parserów opartych na gramatyce BNF w C i jest to zalecana opcja. Większość parserów to klon Lexa i Yacca.

Kroki w budowaniu parsera / intrepretera

  1. Klasyfikuj swoje tokeny na symbole, operatory i słowa kluczowe (słowa kluczowe są operatorami)
  2. Zbuduj swoją gramatykę za pomocą formularza BNF
  3. Napisz funkcje analizatora składni dla swoich operacji
  4. Skompiluj go jako program

Tak więc w powyższym przypadku tokenami dodawania będą dowolne cyfry i znak plus z definicją tego, co zrobić ze znakiem plus w leksyrze

Uwagi i wskazówki

  • Wybierz technikę analizatora składni, która ocenia wartości LALR od lewej do prawej
  • Przeczytaj tę smoczą książkę na temat kompilatorów, aby się tego dowiedzieć. Ja osobiście nie skończyłem książki
  • Ten link dałby super szybki wgląd w Lex i Yacc w Pythonie

Proste podejście

Jeśli potrzebujesz tylko prostego mechanizmu analizy z ograniczonymi funkcjami, zmień swoje wymaganie w wyrażenie regularne i po prostu stwórz całą masę funkcji. Aby to zilustrować, załóżmy prosty parser dla czterech funkcji arytmetycznych. Więc najpierw będziesz wywoływał operatora, a następnie listę funkcji (podobnych do lisp) w stylu, (+ 4 5)a (add [4,5])następnie możesz użyć prostego RegExp, aby uzyskać listę operatorów i symboli, na których operujesz.

Dzięki takiemu podejściu najczęstsze przypadki można łatwo rozwiązać. Minusem jest to, że nie można mieć wielu zagnieżdżonych wyrażeń z wyraźną składnią i nie można mieć łatwych funkcji wyższego rzędu.


2
To jeden z najtrudniejszych możliwych sposobów. Rozdzielanie przebiegów leksykalnych i parsowania itp. - prawdopodobnie jest to przydatne do implementacji analizatora składni o wysokiej wydajności dla bardzo złożonego, ale archaicznego języka. W nowoczesnym świecie parsowanie bez leksemów jest najprostszą domyślną opcją. Kombinatory parsowania lub eDSL są łatwiejsze w użyciu niż dedykowane procesory wstępne, takie jak Yacc.
SK-logic,

Zgadzam się z SK-logic, ale ponieważ wymagana jest ogólna szczegółowa odpowiedź, zasugerowałem Lex i Yacc oraz kilka podstawowych parserów. getopts sugerowany przez Antona jest również prostszą opcją.
Ubermensch,

tak powiedziałem - lex i yacc są jednymi z najtrudniejszych sposobów analizy, a nawet nie dość ogólnymi. Analiza składni bez Lexera (np. Packrat lub zwykły Parsec) jest znacznie prostsza w ogólnym przypadku. A książka o smokach nie jest już zbyt przydatnym wstępem do analizowania - jest zbyt przestarzała.
SK-logic,

@ SK-logic Czy możesz polecić lepiej zaktualizowaną książkę. Wydaje się, że obejmuje wszystkie podstawy dla osoby próbującej zrozumieć przetwarzanie (przynajmniej w moim odczuciu). Jeśli chodzi o lex i yacc, chociaż jest on trudny, jest szeroko stosowany, a wiele języków programowania zapewnia jego implementację.
Ubermensch,

1
@ alfa64: daj nam znać, kiedy kodujesz rozwiązanie oparte na tej odpowiedzi
quentin-starin

7

Po pierwsze, jeśli chodzi o gramatykę lub określanie argumentów, nie wymyślaj własnych. Standardowy GNU stylu jest już bardzo popularne i dobrze znane.

Po drugie, ponieważ używasz przyjętego standardu, nie wymyślaj koła na nowo. Skorzystaj z istniejącej biblioteki, aby zrobić to za Ciebie. Jeśli użyjesz argumentów w stylu GNU, prawie na pewno jest już dojrzała biblioteka w twoim wybranym języku. Na przykład: c # , php , c .

Dobra biblioteka analizująca opcje wydrukuje nawet sformatowaną pomoc dotyczącą dostępnych opcji.

EDYCJA 12/27

Wygląda na to, że czynisz to bardziej skomplikowanym niż jest.

Kiedy patrzysz na linię poleceń, jest to naprawdę dość proste. To tylko opcje i argumenty za tymi opcjami. Jest bardzo mało komplikujących problemów. Opcja może mieć aliasy. Argumenty mogą być listami argumentów.

Jednym z problemów związanych z twoim pytaniem jest to, że tak naprawdę nie określiłeś żadnych reguł dla rodzaju wiersza poleceń, z którym chcesz się uporać. Zasugerowałem standard GNU, a twoje przykłady są bardzo podobne (choć tak naprawdę nie rozumiem twojego pierwszego przykładu ze ścieżką jako pierwszego elementu?).

Jeśli mówimy o GNU, każda pojedyncza opcja może mieć tylko długą i krótką formę (pojedynczy znak) jako aliasy. Wszelkie argumenty zawierające spację muszą być otoczone cudzysłowami. Można połączyć szereg wielu krótkich formularzy. Opcje krótkiej formy muszą być poprzedzone pojedynczym myślnikiem, długie - dwoma myślnikami. Argumentem może być tylko ostatnia z łańcuchowych opcji krótkich formularzy.

Wszystko bardzo proste. Wszystko bardzo często. Zaimplementowano również w każdym języku, który można znaleźć, prawdopodobnie pięć razy.

Nie pisz tego. Użyj tego, co już napisano.

O ile nie masz na myśli czegoś innego niż standardowe argumenty wiersza poleceń, po prostu użyj jednej z WIELU już istniejących, przetestowanych bibliotek, które to robią.

Jaka jest komplikacja?


3
Zawsze, zawsze wykorzystuj społeczność open source.
Spencer Rathbun

próbowałeś getoptionkit?
alfa64

Nie, nie pracowałem w PHP od kilku lat. Mogą też istnieć inne biblioteki php. Użyłem biblioteki parsera wiersza poleceń c #, z którą się połączyłem.
quentin-starin

4

Czy próbowałeś już czegoś takiego jak http://qntm.org/loco ? To podejście jest znacznie bardziej przejrzyste niż jakikolwiek odręczny ad hoc, ale nie będzie wymagało samodzielnego narzędzia do generowania kodu, takiego jak Lemon.

EDYCJA: A ogólną sztuczką związaną z obsługą wierszy poleceń o złożonej składni jest połączenie argumentów z powrotem w pojedynczy ciąg oddzielony spacjami, a następnie parsowanie go poprawnie, tak jakby był wyrażeniem jakiegoś języka specyficznego dla domeny.


+1 fajny link, zastanawiam się, czy jest dostępny na github, czy coś innego. A co z warunkami użytkowania?
hakre

1

Nie podałeś wielu szczegółów na temat swojej gramatyki, tylko kilka przykładów. Widzę tylko, że są jakieś ciągi znaków, białe znaki i (prawdopodobnie w twoim pytaniu jest to obojętne) ciąg znaków podwójnego cudzysłowu, a następnie jeden „;” na końcu.

Wygląda na to, że może to być podobne do składni PHP. Jeśli tak, PHP zawiera analizator składni, możesz ponownie użyć, a następnie zweryfikować bardziej konkretnie. Wreszcie musisz poradzić sobie z tokenami, ale wygląda na to, że jest to po prostu od lewej do prawej, a więc tylko iteracja wszystkich tokenów.

Niektóre przykłady ponownego użycia parsera tokenów PHP ( token_get_all) podano w odpowiedziach na następujące pytania:

Oba przykłady zawierają również prosty parser, prawdopodobnie coś takiego pasuje do twojego scenariusza.


tak, rzuciłem gramatykę, dodam ją teraz.
alfa64

1

Jeśli twoje potrzeby są proste, a oboje macie czas i jesteście tym zainteresowani, pójdę tu na całość i powiem: nie wahaj się napisać własnego parsera. To dobre doświadczenie edukacyjne, jeśli nic więcej. Jeśli masz bardziej złożone wymagania - zagnieżdżone wywołania funkcji, tablice itp. - po prostu pamiętaj, że może to zająć sporo czasu. Jedną z największych zalet samodzielnego rozwijania jest to, że nie będzie problemu z integracją z systemem. Minusem jest oczywiście to, że wszystkie błędy są twoją winą.

Pracuj przeciwko tokenom, nie używaj poleceń zakodowanych na stałe. Potem problem z podobnymi komendami dźwiękowymi znika.

Wszyscy zawsze polecają książkę o smokach, ale zawsze uważałem, że „Pisanie kompilatorów i tłumaczy” Ronalda Maka jest lepszym intro.


0

Napisałem programy, które tak działają. Jednym z nich był bot IRC, który ma podobną składnię poleceń. Istnieje ogromny plik, który jest dużą instrukcją przełączania. Działa - działa szybko - ale jest nieco trudny w utrzymaniu.

Inną opcją, która ma więcej rotacji OOP, jest użycie procedur obsługi zdarzeń. Tworzysz tablicę klucz-wartość z poleceniami i ich dedykowanymi funkcjami. Po wydaniu polecenia sprawdzasz, czy tablica ma podany klucz. Jeśli tak, wywołaj funkcję. To byłoby moje zalecenie dotyczące nowego kodu.


przeczytałem twój kod i jest dokładnie taki sam schemat, jak mój kod, ale jak już powiedziałem, jeśli chcesz, aby inni ludzie mogli z niego korzystać, musisz dodać sprawdzanie błędów i takie tam
alfa64

1
@ alfa64 Proszę dodać wyjaśnienia do pytania zamiast komentarzy. Nie jest do końca jasne, o co dokładnie prosisz, chociaż jest dość jasne, że szukasz czegoś naprawdę konkretnego. Jeśli tak, powiedz nam dokładnie, co to jest. Nie sądzę, że jest to bardzo proste, aby przejść od I think my implementation is very crude and faultydo but as i stated, if you want other people to use, you need to add error checking and stuff... Powiedz nam, co dokładnie znajduje się ropa o nim, a co błędne, to pomoże Ci uzyskać lepsze odpowiedzi.
yannis


0

Sugeruję użycie narzędzia zamiast samodzielnego wdrażania kompilatora lub interpretera. Irony używa C # do wyrażenia gramatyki języka docelowego (gramatyki wiersza poleceń). Opis CodePlex mówi: „Irony to zestaw programistyczny do implementacji języków na platformie .NET”.

Zobacz oficjalną stronę Irony w CodePlex: Irony - .NET Language Implementation Kit .


Jak byś go używał z PHP?
SK-logic,

W pytaniu nie widzę tagu PHP ani odniesienia do PHP.
Olivier Jacot-Descombes

Rozumiem, kiedyś było o PHP, ale teraz przepisane.
SK-logic

0

Moją radą byłoby google dla biblioteki, która rozwiązuje twój problem.

Ostatnio często korzystam z NodeJS, a Optimist jest tym, czego używam do przetwarzania z wiersza poleceń. Zachęcam do wyszukania takiego, którego możesz użyć dla swojego własnego języka. Jeśli nie ... napisz jeden i otwórz go: D Możesz nawet przeczytać kod źródłowy Optimist i przenieść go na wybrany język.


0

Dlaczego nie uprościsz trochę swoich wymagań?

Nie używaj pełnego parsera, ponieważ jest on zbyt skomplikowany, a nawet niepotrzebny w twoim przypadku.

Zrób pętlę, napisz komunikat, który reprezentuje cię „monit”, może być bieżącą ścieżką, którą jesteś.

Poczekaj na ciąg, „przeanalizuj” ciąg i zrób coś w zależności od zawartości ciągu.

Ciąg może „analizować” jak oczekiwanie na linię, w której spacje są separatorami („tokenizer”), a reszta znaków jest zgrupowana.

Przykład.

Program wyświetla (i pozostaje w tym samym wierszu): / user / files / Użytkownik zapisuje (w tym samym wierszu) wyświetla listę;

Twój program wygeneruje listę, kolekcję lub tablicę

list

all;

albo jeśli ";" jest uważany za separator podobny do spacji

/user/files/

list

all

Twój program może zacząć od oczekiwania na pojedynczą instrukcję, bez „potoków” w stylu uniksowym, bez przekierowania w stylu okienkowym.

Twój program może utworzyć słownik instrukcji, każda instrukcja może zawierać listę parametrów.

Wzorzec projektowania poleceń dotyczy twojego przypadku:

http://en.wikipedia.org/wiki/Command_pattern

Ten pseudokod „zwykły c” nie został przetestowany ani ukończony, tylko pomysł na to, jak można to zrobić.

Możesz również uczynić go bardziej obiektowym, a w języku programowania lubisz.

Przykład:


// "global function" pointer type declaration
typedef
  void (*ActionProc) ();

struct Command
{
  char[512] Identifier;
  ActionProc Action; 
};

// global var declarations

list<char*> CommandList = new list<char*>();
list<char*> Tokens = new list<char*>();

void Action_ListDirectory()
{
  // code to list directory
} // Action_ListDirectory()

void Action_ChangeDirectory()
{
  // code to change directory
} // Action_ChangeDirectory()

void Action_CreateDirectory()
{
  // code to create new directory
} // Action_CreateDirectory()

void PrepareCommandList()
{
  CommandList->Add("ls", &Action_ListDirectory);
  CommandList->Add("cd", &Action_ChangeDirectory);
  CommandList->Add("mkdir", &Action_CreateDirectory);

  // register more commands
} // void PrepareCommandList()

void interpret(char* args, int *ArgIndex)
{
  char* Separator = " ";
  Tokens = YourSeparateInTokensFunction(args, Separator);

  // "LocateCommand" may be case sensitive
  int AIndex = LocateCommand(CommandList, args[ArgIndex]);
  if (AIndex >= 0)
  {
    // the command

    move to the next parameter
    *ArgIndex = (*ArgIndex + 1);

    // obtain already registered command
    Command = CommandList[AIndex];

    // execute action
    Command.Action();
  }
  else
  {
    puts("some kind of command not found error, or, error syntax");
  }  
} // void interpret()

void main(...)
{
  bool CanContinue = false;
  char* Prompt = "c\:>";

  char Buffer[512];

  // which command line parameter string is been processed
  int ArgsIndex = 0;

  PrepareCommandList();

  do
  {
    // display "prompt"
    puts(Prompt);
    // wait for user input
      fgets(Buffer, sizeof(Buffer), stdin);

    interpret(buffer, &ArgsIndex);

  } while (CanContinue);

} // void main()

Nie wspomniałeś o swoim języku programowania. Możesz także wspomnieć o dowolnym języku programowania, ale najlepiej „XYZ”.


0

masz przed sobą kilka zadań.

patrząc na twoje wymagania ...

  • Musisz przeanalizować polecenie. To dość łatwe zadanie
  • Musisz mieć rozszerzalny język poleceń.
  • Musisz mieć sprawdzanie błędów i sugestie.

Rozszerzalny język poleceń wskazuje, że wymagany jest DSL. Sugeruję, aby nie tworzyć własnych, ale używać JSON, jeśli rozszerzenia są proste. Jeśli są one złożone, fajna jest składnia wyrażenia s.

Sprawdzanie błędów oznacza, że ​​Twój system wie również o możliwych poleceniach. Byłoby to częścią systemu dowodzenia.

Jeśli I został wdrożenia takiego systemu od podstaw, chciałbym skorzystać z Common Lisp z czytnikiem okrojoną. Każdy token polecenia byłby odwzorowany na symbol, który zostałby określony w pliku RC wyrażenia s. Po tokenizacji byłby oceniany / rozwijany w ograniczonym kontekście, wychwytując błędy, a wszelkie rozpoznawalne wzorce błędów zwracałyby sugestie. Następnie rzeczywiste polecenie zostanie wysłane do systemu operacyjnego.


0

Jest to cecha miła w programowania funkcyjnego , że może być zainteresowany do zbadania.

Nazywa się to dopasowaniem wzorca .

Oto dwa łącza do przykładu dopasowania wzoru w Scali i F # .

Zgadzam się z tobą, że korzystanie ze switchstruktur jest nieco nudne, a szczególnie podobało mi się używanie dopasowania patern podczas implementacji kompilatora w Scali.

W szczególności poleciłbym przejrzeć przykład rachunku lambda na stronie internetowej Scala.

To, moim zdaniem, najmądrzejszy sposób na kontynuację, ale jeśli musisz ściśle trzymać się PHP, utkniesz w „starej szkole” switch.


0

Sprawdź interfejs Apache CLI , wydaje się, że jego głównym celem jest robienie dokładnie tego, co chcesz, więc nawet jeśli nie możesz go użyć, możesz sprawdzić jego architekturę i skopiować to.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.