CODEWITHSUNDEEP
parsingprolog
user1794576
user1794576

Reputation: 43

Parser Implementation

Hi I am trying to implement a parser for a simple language with grammar like this.

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

I have the first two done, how would I write the type grammar?

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

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

Upvotes: 4

Views: 246

Answers (3)

CapelliC
CapelliC

Reputation: 60034

You miss statements rule!

Anyway, DCG rules are just plain syntax sugar on Prolog, then you can use any Prolog feature you like. If you need to keep the grammar compact:

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

Braces allow to mix generic Prolog with grammar rules.

As @false noted, your grammar is useful only if you have a tokenizer, that splits your input and discards whitespaces. Or you could handle that more directly, using this schema (beware, untested code):

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 ; []).

Upvotes: 1

thanos
thanos

Reputation: 5858

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

(actually ' are not required)

You could use | or ; but that would complicate the way you return the type you found.

Upvotes: 1

false
false

Reputation: 10142

Your grammar might be underspecified. In fact you do not define how keywords are separated from other tokens like identifiers. There are programming languages, where you do not need to separate keywords from identifiers. And there are other programming languages where some whitespace or layout character is needed.

In your case, is "varaasint" a valid declaration? Your grammar suggests it. Or do you have to write "var a as int".

You might want to look into this answer for more.

Upvotes: 2

Related Questions