dimare@ucla-cs.UUCP (09/20/85)
I'm writing a little parser for a Pascal like language. I was going to copy Wirth's grammar into a DCG Prolog program, but I noticed that left recursion can't be used. If you have a rule like: a --> a, [+], b. a --> b. b --> [b]. it translates into: a(A, B) :- a(A, C), 'C'(C, +, D), b(D, B). 'C'([H|T],H,T). Any goal of the form a(Sentence,[]) would make the above rule recurse until end_of_stack. (Yes, a([b,+,b],[]) doesn't work either: try it!). My problem is that the grammars I know for parsing expressions are left recursive. The example in most Prolog manuals uses left recursion. I ran it, and I got the following result (I include the code at the end of the message): | ?- expr(Z,"2-3-4",[]). Z = 3 ; no | ?- Z is 2-3-4. Z = -5 ; no | ?- halt. Obviously, the 'standard' example is wrong. My question is: Does any body know a way to do expressions using DCGs that doesn't make the grammar look like a plate of spaghetti? I know I could translate my grammar into Griebach Normal Form (or $%#!"%#$" Normal Form, for that mater), but I could also as well write the whole parser in 8080 assembly language. Here's the grammar: Script started on Thu Sep 19 15:16:07 1985 h[2:101] c dcg0 % File : /usr/lib/prolog/teach/dcg0 % Author : lost in the mists of time % Updated: 23 Nov 1983 % Purpose: the standard example of using Prolog grammar rules % This is a simple grammar which parses an arithmetic expression (of digits and % operators) and computes its value. expr(Z) --> term(X), "+", expr(Y), {Z is X+Y}. expr(Z) --> term(X), "-", expr(Y), {Z is X-Y}. expr(Z) --> term(Z). term(Z) --> number(X), "*", term(Y), {Z is X*Y}. term(Z) --> number(X), "/", term(Y), {Z is X/Y}. term(Z) --> number(Z). number(C) --> "+", number(C). number(C) --> "-", number(X), {C is -X}. number(X) --> [C], {48=<C, C=<57, X is C-48}. % In the last rule, C is the ASCII code of a digit. % The question % % | ?- expr(Z,"-2+3*5+1",[]). % % will compute Z=14. The two extra arguments here are because grammar rules % are in fact merely 'syntactic sugar' for ordinary Prolog clauses. Each grammar % rule takes an input string, analyses some initial portion and produces an % output portion (the rest, possibly enlarged a bit) for further analysis. h[2:102] uprolog CProlog version 1.4d.edai | ?- [dcg0]. dcg0 consulted 1208 bytes 0.78333 sec. yes | ?- expr(Z,"2-3-4",[]). Z = 3 ; no | ?- Z is 2-3-4. Z = -5 ; no | ?- halt. [ Prolog execution halted ] h[2:103] script done on Thu Sep 19 15:18:16 1985 Adolfo ///
vantreeck@logic.DEC (09/23/85)
>Newsgroups: net.lang.prolog >Path: decwrl!pyramid!nsc!hplabs!sdcrdcf!ucla-cs!dimare >Subject: DCGs + Left Recursion = (:-[) ! >Posted: 19 Sep 85 23:38:57 GMT >Organization: UCLA Computer Science Department >I'm writing a little parser for a Pascal like language. >I was going to copy Wirth's grammar into a DCG Prolog >program, but I noticed that left recursion can't be used. You are correct in your assertion that most PROLOGs' DCGs do not handle left recursion. That's because they're simple top down parsers. There is a PROLOG DCG parser that uses bottom up parsing (and can handle left recursions). The parser is called BUP. Need I say it stands for Bottom Up Parser? I don't have the references here at work - the papers are a couple of years old. I'm sure your UCLA libarary can do a computer search on BUP. Off the top of my head -- A brief description can be found in a book by Dahl, Natural Language Understanding with Logic - it's a collection of papers from a 1984 symposium in France. The articles I've read on BUP tend to be of the "Gee, isn't this wonderful!" variety, rather than delving into enough implementation detail that someone could use it as a guide to writing a BUP. If anyone finds a paper that gives an in depth description of the implementation details, please post it to the net or send mail! -George