Asp Forum - cl-yacc is cool

Jim Newton

12/10/2015 9:38:00 AM

Has anyone used cl-yacc? I just spent a couple of days using it. I've never used yacc before,
not even c-yacc, so part of my slowness was to learn some of the concepts. But It is really cool.
It quite very easy to use.

I used it to write a parser for the graph viz dot language using
the grammar given here http://www.graphviz.org/doc/info....
Part of my slowness was due to a subtle error in the grammar in the dot documentation,
which I still need to report to the graphviz maintainers.

The cl-yacc based program converts a .dot file to s-expressions.

I had to write my own lexer for the dot language, which wasn't very difficult. Apparently there
is a cl-lex which exists. If anyone has used it, how was it?

If anyone wants a copy of the program, please let me know.

Many thanks to Juliusz Chroboczek for writing cl-yacc.

14 Answers

Jim Newton

12/10/2015 3:27:00 PM

Can I ask a question in case someone has used cl-yacc enough to know the answer.

In the cl-yacc documentation there is the :precedence option for define-grammar.
The documentation says the following:

:precedence
The value of this option should be a list of items of the form (associativity . terminals), where associativity is one of :left, :right or :nonassoc, and terminals is a list of terminal symbols. Associativity specifies the associativity of the terminals, and earlier items will give their elements a precedence higher than that of later ones.

Is this accurate? I.e., may I only describe precedence for terminal symbols? Or can I also specify precedence for production rules?
In my case I'm using juxtaposition as an operation and I want it to have higher precedence than some other operator.
juxtaposition does not have a terminal symbol.

I hope this is omission in the documentation.

I have defined a :precedence for my juxtaposition rule, but It looks to me like cl-yacc ignores it and does not complain.
Maybe I have an error somewhere else in my grammar definition.

Kind regards
Jim

Pascal J. Bourguignon

12/10/2015 3:50:00 PM

Jim Newton <jimka.issy@gmail.com> writes:

> Can I ask a question in case someone has used cl-yacc enough to know the answer.
>
> In the cl-yacc documentation there is the :precedence option for define-grammar.
> The documentation says the following:
>
> :precedence
> The value of this option should be a list of items of the form
> (associativity . terminals), where associativity is one of :left,
> :right or :nonassoc, and terminals is a list of terminal
> symbols. Associativity specifies the associativity of the terminals,
> and earlier items will give their elements a precedence higher than
> that of later ones.
>
>
> Is this accurate? I.e., may I only describe precedence for terminal
> symbols? Or can I also specify precedence for production rules?

> In my case I'm using juxtaposition as an operation and I want it to
> have higher precedence than some other operator. juxtaposition does
> not have a terminal symbol.

This should translate in your grammar.

It is precisely because non-terminals name grammar rules and therefore
can have no corresponding terminal symbols, that their precedence should
be established thru the grammar rules.

> I hope this is omission in the documentation.
>
> I have defined a :precedence for my juxtaposition rule, but It looks
> to me like cl-yacc ignores it and does not complain. Maybe I have an
> error somewhere else in my grammar definition.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Jim Newton

12/10/2015 4:03:00 PM

Hi Pascal, you didn't answer explicitly, but it sounds like, you think cl-yacc does not support what I want, and that I need to change my grammar.

I didn't write the grammar. I'm using the one from: http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regex...

Do you think there is a reduce/reduce conflict in this grammar associated with the
<union> and <concatenation> rules?

Do can you suggest a way to change the <union> and <concatenation> rule to eliminate the
precedence issue? I want <concatenation> to have higher precedence than <union>.

Jim Newton

12/10/2015 4:07:00 PM

Here is the grammar as I've encoded it. I get a reduce/reduce conflict which looks to me like a precedence problem.

; caught WARNING:
; Reduce/Reduce conflict on terminal <PAREN-CLOSE> in state 3, #<YACC::REDUCE-ACTION <UNION> (3)> and #<YACC::REDUCE-ACTION <CONCATENATION> (1)> #<PRODUCTION <UNION> --derives--> <RE> <OR> <SIMPLE-RE>> #<PRODUCTION <CONCATENATION> --derives--> <SIMPLE-RE>>
;

;; <RE> ::= <union> | <simple-RE>
;; <union> ::= <RE> "|" <simple-RE>
;; <simple-RE> ::= <concatenation> | <basic-RE>
;; <concatenation> ::= <simple-RE> <basic-RE>
;; <basic-RE> ::= <star> | <plus> | <elementary-RE>
;; <star> ::= <elementary-RE> "*"
;; <plus> ::= <elementary-RE> "+"
;; <elementary-RE> ::= <group> | <any> | <eos> | <char> | <set>
;; <group> ::= "(" <RE> ")"
;; <any> ::= "."
;; <eos> ::= "$"
;; <char> ::= any non metacharacter | "\" metacharacter
;; <set> ::= <positive-set> | <negative-set>
;; <positive-set> ::= "[" <set-items> "]"
;; <negative-set> ::= "[^" <set-items> "]"
;; <set-items> ::= <set-item> | <set-item> <set-items>
;; <set-items> ::= <range> | <char>
;; <range> ::= <char> "-" <char>
(yacc:define-parser *regexp-parser*
;; RE grammar borrowed from
;; Perl Style Regular Expressions in Prolog
;; CMPT 384 Lecture Notes
;; Robert D. Cameron
;; November 29 - December 1, 1999
;; http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regex...
(:start-symbol <RE>)
(:print-lookaheads t)
(:print-goto-graph t)
(:print-states t)
(:terminals (<char> * - ? + [ ] |.| <paren-open> <paren-close> <or> ))
(:precedence ((:left <concatenation>)
(:left <or>)))

;; <RE> ::= <union> | <simple-RE>
(<RE>
<union>
<simple-RE>)

;; <union> ::= <RE> "|" <simple-RE>
(<union>
(<RE> <or> <simple-RE> (lambda (re1 or re2)
(declare (ignore or))
`(:or ,re1 ,re2))))

;; <simple-RE> ::= <concatenation> | <basic-RE>
(<simple-RE>
<concatenation>
<basic-RE>)

;; <concatenation> ::= <simple-RE> <basic-RE>
(<concatenation>
<simple-RE>
<basic-RE>)

;; <basic-RE> ::= <star> | <plus> | <elementary-RE>
(<basic-RE>
<star>
<plus>
<elementary-RE>)

;; <star> ::= <elementary-RE> "*"
(<star>
(<elementary-RE> * (lambda (re _)
(declare (ignore _))
`(:0-* ,re))))

;; <plus> ::= <elementary-RE> "+"
(<plus>
(<elementary-RE> + (lambda (re _)
(declare (ignore _))
`(:1-* ,re))))

;; <elementary-RE> ::= <group> | <any> | <eos> | <char> | <set>
(<elementary-RE>
<group>
<any>
<eos>
<char>
<set>)

;; <group> ::= "(" <RE> ")"
(<group>
( <paren-open> <RE> <paren-close> (lambda (_ re __)
(declare (ignore _ __))
re)))

;; <any> ::= "."
(<any>
(|.| (constantly t)))

;; <eos> ::= "$"
(<eos>
|$|)

;; <char> ::= any non metacharacter | "\" metacharacter
;; terminal symbol

;; <set> ::= <positive-set> | <negative-set>
(<set>
<positive-set>
<negative-set>)

;; <positive-set> ::= "[" <set-items> "]"
(<positive-set>
([ <set-items> ] (lambda ([ set-items ])
(declare (ignore [ ] ))
`(member ,@set-items))))

;; <negative-set> ::= "[^" <set-items> "]"
(<negative-set>
([ ^ <set-items> ] (lambda (&rest args)
(error "negative-set not supported: ~A" args))))

;; <set-items> ::= <set-item> | <set-item> <set-items>
(<set-items>
(<set-item>)
(<set-item> <set-items> #'cons))

;; <set-items> ::= <range> | <char>
(<set-items>
<range>
<char>)

;; <range> ::= <char> "-" <char>
(<range>
(<char> - <char> (lambda (&rest args)
(error "range not supported: ~A" args))))

)

Pascal J. Bourguignon

12/10/2015 4:30:00 PM

Jim Newton <jimka.issy@gmail.com> writes:

> Hi Pascal, you didn't answer explicitly, but it sounds like, you think
> cl-yacc does not support what I want, and that I need to change my
> grammar.
>
> I didn't write the grammar. I'm using the one from: http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regex...
>
> Do you think there is a reduce/reduce conflict in this grammar associated with the
> <union> and <concatenation> rules?
>
> Do can you suggest a way to change the <union> and <concatenation> rule to eliminate the
> precedence issue? I want <concatenation> to have higher precedence than <union>.

Well, I have very little patience for LALR conflicts. I just rewrite
the grammar for LL(1) and use a simple recursive descent parser
generator. Granted, for some horrible languages such as C or C++, such
a LALR->LL(1) transformation is rather teddious, but LL(1) has several
other advantages too (eg. better error messages and error recovery).

Also, nowadays, you may want to use a more modern parser generator, such
as esrap or a PEG generator, which let you write even more easily the
grammars, it seems (I haven't tried them yet).

I'll give you a hint: gcc uses a recursive descent parser written by
hand.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Kaz Kylheku

12/10/2015 8:03:00 PM

On 2015-12-10, Jim Newton <jimka.issy@gmail.com> wrote:
> Here is the grammar as I've encoded it. I get a reduce/reduce
> conflict which looks to me like a precedence problem.
>
>
> ; caught WARNING:
> ; Reduce/Reduce conflict on terminal <PAREN-CLOSE> in state 3,
> #<YACC::REDUCE-ACTION <UNION> (3)> and #<YACC::REDUCE-ACTION
> <CONCATENATION> (1)> #<PRODUCTION <UNION> --derives--> <RE> <OR>
> <SIMPLE-RE>> #<PRODUCTION <CONCATENATION> --derives--> <SIMPLE-RE>>

That diagnostic looks buggy to me. Your <concatenation> does not derive
<simple-re> -- certainly not directly; it derives <simple-re>
<basic-re>. (Of course it reduces to <simple-re> in the other
direction, but that's not derivation).

<concatenation> could derive <simple-re> indirectly if <basic-re> derived
the empty string, but I don't see that anywhere.

Jim Newton

12/11/2015 9:27:00 AM

>
> That diagnostic looks buggy to me. Your <concatenation> does not derive
> <simple-re> -- certainly not directly; it derives <simple-re>
> <basic-re>. (Of course it reduces to <simple-re> in the other
> direction, but that's not derivation).
>
> <concatenation> could derive <simple-re> indirectly if <basic-re> derived
> the empty string, but I don't see that anywhere.

Sorry Kaz, if I don't understand. Are you suggesting it is probably a bug in MY encoding of the
grammar (very likely in my opinion), or in the published grammar on
http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regex...
or a bug in cl-yacc?

Jim Newton

12/11/2015 9:35:00 AM

> That diagnostic looks buggy to me. Your <concatenation> does not derive
> <simple-re> -- certainly not directly; it derives <simple-re>
> <basic-re>. (Of course it reduces to <simple-re> in the other
> direction, but that's not derivation).
>
> <concatenation> could derive <simple-re> indirectly if <basic-re> derived
> the empty string, but I don't see that anywhere.

I FOUND A BUG IN MY GRAMMAR!!! yippieeeee

The <concatenation> rule from the published grammar is
<concatenation> ::= <simple-RE> <basic-RE>

I had encoded it as
(<concatenation>
<simple-RE>
<basic-RE>)

which means a <concatenation> is either a <simple-RE> or a <basic-RE>.

I should have that <concatenation> is a concatenation of <simple-RE> and <basic-RE>.
I should encode this as

(<concatenation>
(<simple-RE> <basic-RE>))

Jim Ottaway

12/11/2015 11:32:00 AM

>>>>> Jim Newton <jimka.issy@gmail.com> writes:
> I FOUND A BUG IN MY GRAMMAR!!! yippieeeee

I think I've found another bug: Shouldn't

(<set-items>
<range>
<char>)

be

(<set-item>
<range>
<char>)

?

Otherwise there's no rule for <set-item>.

Actually, it looks as though this got carried across from a typo in the
grammar on the webpage you cite. (Unless I'm mistaken, of course, which
I could be because parsers et al. aren't my forte.)

Thanks, incidentally, for posting on this topic: you've reminded me to
have a look at cl-yacc which I'd been meaning to do for ages.

Yours sincerely,
--
Jim Ottaway

Kaz Kylheku

12/11/2015 3:47:00 PM

On 2015-12-11, Jim Newton <jimka.issy@gmail.com> wrote:
>
>> That diagnostic looks buggy to me. Your <concatenation> does not derive
>> <simple-re> -- certainly not directly; it derives <simple-re>
>> <basic-re>. (Of course it reduces to <simple-re> in the other
>> direction, but that's not derivation).
>>
>> <concatenation> could derive <simple-re> indirectly if <basic-re> derived
>> the empty string, but I don't see that anywhere.
>
> I FOUND A BUG IN MY GRAMMAR!!! yippieeeee

Aha, so the diagnostic isn't lying after all.

You see, it pays to read them diagnostics.

> The <concatenation> rule from the published grammar is
> <concatenation> ::= <simple-RE> <basic-RE>
>
> I had encoded it as
> (<concatenation>
> <simple-RE>
> <basic-RE>)

If simply listing symbols together mmeans alternation, I would call that
a pretty bad S-exp notation for writing grammars.

CL-YACC should consider just one s-exp for one production. That is to
say, alternative productions should be written as separate rules:

(<concatenation> <simple-re>)
(<concatenation> <basic-re>)

Then,

(foo a b c)

means "foo := a b c".

> I should have that <concatenation> is a concatenation of <simple-RE> and <basic-RE>.
> I should encode this as
>
> (<concatenation>
> (<simple-RE> <basic-RE>))

See? Just because you added a nesting level, with no operator, the
juxtaposition of symbols changes meaning from "alternative" to "consecutive".

Ouch!

comp.lang.lisp

cl-yacc is cool

Jim Newton

Jim Newton

Pascal J. Bourguignon

Jim Newton

Jim Newton

Pascal J. Bourguignon

Kaz Kylheku

Jim Newton

Jim Newton

Jim Ottaway

Kaz Kylheku

x Login to ForumsZone