Implementacja parsera

Question

Witam Próbuję zaimplementować parser dla prostego języka z taką gramatyką.

program ::= "program" declarations "begin" statements "end" 
declaration ::= "var" ident "as" type 
type ::= "string" | "int" 

Mam dwie pierwsze wykonane, jak mogę napisać gramatykę typu?

program(prog(DECLS, STATS)) --> 
[ 'program' ], declarations(DECLS), 
[ 'begin' ], statements(STATS), [ 'end' ]. 

declaration(decl(IDENT, TYPE)) --> 
[ 'var' ], ident(IDENT), [ 'as' ], type(TYPE). 

Answer 1

type(string) --> ['string']. 
type(int) --> ['int']. 

(faktycznie ' nie są wymagane)

Można użyć | lub ; ale to komplikuje sposób zwraca typ znalazłeś.

Answer 2

Twoja gramatyka może być niedookreślona. W rzeczywistości nie definiujesz sposobu oddzielania słów kluczowych od innych tokenów, takich jak identyfikatory. Istnieją języki programowania, w których nie trzeba oddzielać słów kluczowych od identyfikatorów. Istnieją również inne języki programowania, w których wymagany jest jakiś biały znak lub układ.

Czy w twoim przypadku "varaasint" jest prawidłową deklaracją? Twoja gramatyka sugeruje to. Czy musisz napisać "var a as int".

Możesz zajrzeć do this answer for more.

Answer 3

Tęsknisz za zasadą statements!

W każdym razie, zasady DCG to zwykły cukier składniowy w Prologu, możesz użyć dowolnej funkcji Prolog, którą lubisz. Jeśli chcesz zachować gramatykę zwartą:

type(type(T)) --> [T], {memberchk(T, [int, string])}. 

Szelki pozwalają na mieszanie ogólnych Prologów z zasadami gramatyki.

Jak zauważyłeś @false, twoja gramatyka jest przydatna tylko wtedy, gdy masz tokenizera, który dzieli twoje dane wejściowe i odrzuca wszelkie spacje w postaci. Czy można sobie z tym poradzić bardziej bezpośrednio, za pomocą tego schematu (uwaga, kod niesprawdzone):

program(prog(DECLS, STATS)) --> 
    s, "program", s, declarations(DECLS), 
    s, "begin", s, statements(STATS), s, "end", s. 

declaration(decl(IDENT, TYPE)) --> 
    "var", s, ident(IDENT), s, "as", s, type(TYPE). 

declarations([D|Ds]) --> declaration(D), declarations(Ds). 
declarations([]) --> []. 

type(type(int)) --> "int". 
type(type(string)) --> "string". 

% skip 1 or more whitespace 
s --> (" " ; "\n"), (s ; []).