[climacs-devel] grammar definition

[Nicolas Sceaux]

Robert Strandh <strandh at labri.fr> writes:

> You may want to start with a protocol (in the sense of Keene) for
> manipulating grammars; then you can define syntax to simplify common
> cases.  For instance, you most likely would want the grammar to be
> able to evolve programmatically.  There should be some examples of
> `add-rule' in the other syntax modules that show this idea. 

An attempt to write protocol for LR syntax, as defined in
lisp-syntax.lisp today (the descriptions, when they are mine, are, hm,
minimal):

lr-syntax [protocol class]
  Base class for syntaxes using a LR parser.

parser-symbol [protocol class]
  Base class for parse trees, including lexemes.

* Lexer

lexer-state [protocol class]
  These states are used to determine how the lexer should behave.

define-lexer-state name superclasses &body body [macro]
  Define a lexer-state subclass (lexer-state is prepended to the
  superclass list).

skip-inter syntax state scan [generic function]
  Advance scan until the beginning of a new lexeme.
  Return T if one can be found and NIL otherwise.

lexeme [class]
  ...

lex syntax state scan [generic function]
  Return the next lexeme starting at scan.

* Parser

parser-state [protocol class]
  Base class for LR parser states.

define-parser-state name superclasses &body body [macro]
  Define a parser-state subclass and a singleton instance with the same
  name.
  (Side question: shouldn't parser-state be added to the superclass list
  by the macro, rather than by the user? as is done in
  define-lexer-state)

action syntax parser-state lexeme [generic function]
  This function is called after the lexer has returned a lexeme to the
  parser, which current state is parser-state. It returns a
  parser-symbol.

define-action syntax (parser-state lexeme) body [macro]
  Define an action method for syntax, parser-state and lexeme.

reduce-fixed-number [macro]
  ...
reduce-until-type [macro]
  ...
reduce-all [macro]
  ...
  NOTE: I see that SYNTAX is used in there expansion, without
  introducing a binding for it. Isn't that a problem?
done [tag]
  ...

new-state syntax parser-state parser-symbol [generic function]
  This function is called after the parser, which current state is
  parser-state, has reached parser-symbol, and return the new parser
  state.

define-new-state syntax (parser-state parser-symbol) new-parser-state
  Define what the new state of the parser should be when it reaches
  parser-symbol while its current state is parser-state.

* Display

display-parse-tree parse-symbol syntax pane
  ...

> Perhaps a compromise would be to specify a rule pretty much the
> standard way, but to allow for a state name to be inserted between two
> parser symbols, for instance:
>
>    (list -> left-parenthesis-lexeme {the-state-we-want-to-be-in} ...)
>
> or something like that.  

add-rule syntax (nonterminal -> &rest arguments) [macro]
  Create a parser rule for syntax.
  arguments should look like: initial-state [symbol next-state]+ [:EOF]?
  :EOF is used to signal that the reduction to nonterminal applies when
  the end of buffer is reached.
  nonterminal -> initial-state symbol1 state1 symbol2 state2 ... symboln staten
  means that starting from the parser state initial-state, when symbol1
  is reached, the parser changes to state state1; then, being in state
  state1, if symbol2 is reached, the parser changes to state state2,
  etc. Finally, the parse tree is reduced to nonterminal. The parser is
  then in state staten.
  (reading myself, I do realize that I'm not really clear)

(add-rule lisp-syntax
 (complete-list-form -> form-may-follow left-parenthesis-lexeme
                        |( form* |      comment
                        |( form* |      form
                        |( form* |      right-parenthesis-lexeme
                        |( form* ) |))
==>
(PROGN (DEFINE-NEW-STATE LISP-SYNTAX (FORM-MAY-FOLLOW LEFT-PARENTHESIS-LEXEME)
        |( form* |)
       (DEFINE-NEW-STATE LISP-SYNTAX (|( form* | COMMENT) |( form* |)
       (DEFINE-NEW-STATE LISP-SYNTAX (|( form* | FORM) |( form* |)
       (DEFINE-NEW-STATE LISP-SYNTAX (|( form* | RIGHT-PARENTHESIS-LEXEME)
        |( form* ) |)
       (DEFINE-ACTION LISP-SYNTAX (|( form* ) | T)
        (REDUCE-UNTIL-TYPE COMPLETE-LIST-FORM LEFT-PARENTHESIS-LEXEME)))

(add-rule lisp-syntax
 (incomplete-list-form -> form-may-follow left-parenthesis-lexeme
                          |( form* | comment
                          |( form* | form
                          |( form* | :EOF))))
==>
(PROGN (DEFINE-NEW-STATE LISP-SYNTAX (FORM-MAY-FOLLOW LEFT-PARENTHESIS-LEXEME)
        |( form* |)
       (DEFINE-NEW-STATE LISP-SYNTAX (|( form* | COMMENT) |( form* |)
       (DEFINE-NEW-STATE LISP-SYNTAX (|( form* | FORM) |( form* |)
       (DEFINE-ACTION LISP-SYNTAX (|( form* | (EQL NIL))
        (REDUCE-UNTIL-TYPE INCOMPLETE-LIST-FORM LEFT-PARENTHESIS-LEXEME)))

That would cover most of the rules in lisp-syntax (ie, all of them,
except the error and top-level ones).

nicolas