style Q: use keywords for my LALR parser generator?

style Q: use keywords for my LALR parser generator?

[Matt Wette]

[-- Attachment #1: Type: text/plain, Size: 1600 bytes --]

Hi Folks,

I was interested in generating parsers in scheme so I has a look at (system base lalr).  I was not crazy about the syntax:  it's not really scheme-like and did not support in-rule actions (e.g., "foo { $$ = $3 + $2; } bar").  In addition, the code is, according to its author, a direct c-to-scheme translation from the Bison source, and makes heavy use of defmacro.

So, just for fun, I have started coding my own lalr parser generator.  (Many years ago I read the dragon book cover-to-cover and worked on my own yacc in C.)  Here is an example illustrating the basic syntax I have designed for a parser specification:
   
  (lalr1-spec
   (token integer float)
   (start expr)

   (grammar
    (expr
     (expr #\+ term (+ $1 $3))
     (expr #\- term (- $1 $3)))
     )
    (term
     (term #\* factor (* $1 $3)))
     (term #\/ factor (/ $1 $3)))
     )
    (factor (integer) (float))
    )))

Note that right-hand-side elements enclosed in paren's are interpreted as actions.  Not sure this will stay.

Now in the code I will need to be going through the productions checking if symbols are terminals (i.e., declared with "token").   This could end up being inefficient.  In order to make the code more efficient I am considering using keywords (e.g., test for terminal with "keyword?").  However, I wonder if using keywords instead of "token" declarations would be considered "bad form."  For example, in the above, replace
 
    (token integer float)
    ...
    (factor (integer) (float))
with
        (factor (#:integer) (#:float))

Comments?

Matt

[-- Attachment #2: Type: text/html, Size: 3302 bytes --]

Re: style Q: use keywords for my LALR parser generator?

[Thien-Thi Nguyen]

[-- Attachment #1: Type: text/plain, Size: 1168 bytes --]

() Matt Wette <mwette@alumni.caltech.edu>
() Sun, 28 Dec 2014 16:23:28 -0800

   Now in the code I will need to be going through the
   productions checking if symbols are terminals (i.e., declared
   with "token").  This could end up being inefficient.

Why could it end up being inefficient?

   In order to make the code more efficient I am considering
   using keywords (e.g., test for terminal with "keyword?").
   However, I wonder if using keywords instead of "token"
   declarations would be considered "bad form."  For example, in
   the above, replace

       (token integer float)
       ...
       (factor (integer) (float))
   with
       (factor (#:integer) (#:float))

   Comments?

I like keywords because they font-lock (in Emacs) nicely, but
that's merely aesthetics.  I find working w/ keywords as data
slightly balky, and of late, have been migrating keyword-ful
code to use symbols, instead.

-- 
Thien-Thi Nguyen
   GPG key: 4C807502
   (if you're human and you know it)
      read my lisp: (responsep (questions 'technical)
                               (not (via 'mailing-list)))
                     => nil

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: style Q: use keywords for my LALR parser generator?

[Matt Wette]

[-- Attachment #1: Type: text/plain, Size: 521 bytes --]


On Dec 29, 2014, at 3:23 AM, Thien-Thi Nguyen <ttn@gnu.org> wrote:

> () Matt Wette <mwette@alumni.caltech.edu>
> () Sun, 28 Dec 2014 16:23:28 -0800
> 
>   Now in the code I will need to be going through the
>   productions checking if symbols are terminals (i.e., declared
>   with "token").  This could end up being inefficient.
> 
> Why could it end up being inefficient?
> 


(define (non-terminal? term tokl)
  (and (symbol? term) (not (memq term tokl))))

versus

(define (non-terminal? term)
  (symbol? term))




[-- Attachment #2: Type: text/html, Size: 1283 bytes --]

Re: style Q: use keywords for my LALR parser generator?

[Thien-Thi Nguyen]

[-- Attachment #1: Type: text/plain, Size: 865 bytes --]

() Matt Wette <mwette@alumni.caltech.edu>
() Mon, 29 Dec 2014 06:05:35 -0800

   (define (non-terminal? term tokl)
     (and (symbol? term) (not (memq term tokl))))

If ‘tokl’ contains only symbols, then the first sub-expression
‘(symbol? term)’ is superfluous, thanks to ‘memq’.

   (define (non-terminal? term)
     (symbol? term))

How about using an object property?

 (define terminal (make-object-property))
 
 (define (non-terminal? obj)
   (not (terminal obj)))

You would have to ‘(set! (terminal OBJ) #t)’ for every terminal,
of course.  This works fine w/ either symbols or keywords, btw.

-- 
Thien-Thi Nguyen
   GPG key: 4C807502
   (if you're human and you know it)
      read my lisp: (responsep (questions 'technical)
                               (not (via 'mailing-list)))
                     => nil

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: style Q: use keywords for my LALR parser generator?

[Matt Wette]

On Dec 29, 2014, at 7:43 AM, Thien-Thi Nguyen <ttn@gnu.org> wrote:
> () Matt Wette <mwette@alumni.caltech.edu>
> () Mon, 29 Dec 2014 06:05:35 -0800
> 
>   (define (non-terminal? term tokl)
>     (and (symbol? term) (not (memq term tokl))))
> 
> If ‘tokl’ contains only symbols, then the first sub-expression
> ‘(symbol? term)’ is superfluous, thanks to ‘memq’.

Yes, thanks.

>   (define (non-terminal? term)
>     (symbol? term))
> 
> How about using an object property?
> 
> (define terminal (make-object-property))
> 
> (define (non-terminal? obj)
>   (not (terminal obj)))
> 
> You would have to ‘(set! (terminal OBJ) #t)’ for every terminal,
> of course.  This works fine w/ either symbols or keywords, btw.

Thanks.   I did not know about object properties.  Will check.

Matt