Add GRAMMAR structure and dependencies between grammars

[scymtym]

This is a prototype implementation of package-like grammars. It is prototypical in the sense that much cleanup and some refactoring is necessary. However, I wanted to try and get some feedback before polishing this any further. Thanks for taking the time to consider this.

Commit message:

* Partly based on menschenkindlein's
  implementation
  (Menschenkindlein/esrap@63baec4e20591d3c1517fae88a364de8a39ebb12).

* Grammar objects are a bit like CL packages:

  * they have a name and optional :DOCUMENTATION
  * they can :USE other grammars
  * they act as containers for rules
  * redefinition is allowed and preserves existing rules

* Changed interface:

  * GRAMMAR-NOT-FOUND-{ERROR,WARNING} [condition]
  * RULE-NOT-FOUND-{ERROR,WARNING}    [condition]

  * GRAMMAR-NAME                      [function]
  * GRAMMAR-DEPENDENCIES              [function]
  * GRAMMAR-RULES                     [function]

  * DEFGRAMMAR                        [macro]
  * IN-GRAMMAR                        [macro]

  * MAKE-GRAMMAR                      [function]
  * FIND-GRAMMAR                      [function]
  * (SETF FIND-GRAMMAR)               [function]

  * DEFGRAMMAR, DEFRULE and PARSE signal full warnings at compile time
    when constant references to grammars or rules cannot be resolved.

  * IMPORTANT: In addition, all user-visible -rule functions take a
    grammar designator as their first argument.

* Changed implementation:

  * DEFGRAMMAR, IN-GRAMMAR and DEFRULE produce code which is evaluated
    at compile-, load- and runtime. This is necessary in order to be
    able to define and use a grammar in the same file.

  * FIND-RULE traverses used grammars to find the requested rule.

  * The new functions UPDATE-RULE-DEPENDENCIES, RECOMPILE-CELL are
    called after adding/removing rules/used grammars to update
    dependencies and recompile rules.

  * Rule dependencies are expressed in terms of referencing rule
    cells, not symbols.

* New tests for grammar objects and related lookup and redefinition
  issues have been added.

* Documentation has been extended.

* Examples:

  * example-sexp.lisp now uses a separate grammar called SEXP

  * example-sexp-xml.lisp contains a new grammar called XML which uses
    the SEXP grammar to demonstrate grammar dependencies (originally
    written by Menschenkindlein)

There are design decision, for which I could use some advice:

1. Is backwards compatibility to the previous

(parse RULE STRING)

interface required?

1. Rule names are currently processed using STRING. This allows clients to write

(parse '#:some-grammar '#:some-rule TEXT)

. It also frees grammar writers from exporting rule names as symbols. However, it could lead to clashes between rule names in the USE-closure of some grammar. It also prevents "private" rules.

1. Should operations on grammars accept grammar objects and grammar designators or should the idiom instead always be

(grammar-name (find-grammar GRAMMAR-DESIGNATOR))

?

1. Should operations on rules accept grammar and rule designators as in

(rule-dependencies GRAMMAR-DESIGNATOR RULE-DESIGNATOR)

or should these operations accept rule objects as in

(rule-dependencies (find-rule GRAMMAR-DESIGNATOR RULE-DESIGNATOR))

or even

(rule-dependencies (find-rule (find-grammar GRAMMAR-DESIGNATOR) RULE-DESIGNATOR))

?

5. Should circular dependencies between grammars be allowed? Currently, they signal an error.
6. The *non-existent* tests use some compilation/signal-related trickery which can probably be improved.
7. Redefinition of whole grammars (via (setf (find-grammar ...) nil) and then (defgrammar ...)) after (parse ...) calls have been compile-time optimized can lead to an old definition of a rule being used.

[nikodemus]

very nice work! Much kudos.

This is based on a very quick look, so a grain of salt may be needed:

Easy answers first.

• Accepting designators is good.
• No circular dependencies sounds good to me.
• Optimizations leading to old rules being used are in principle fine, but I would like to have that behind a flag so it can be turned off for debugging. No need to export or document the flag.

Less easy:

Overall I value backwards compatibility highly. If keeping it doesn't make things clearly worse or implementation much harder, I would keep it. Therefore I would prefer ADD-RULE and &co to default to grammar at runtime, and have that as either a keyword or an optional argument. Analogously to how INTERN &co work.

DEFRULE on the other hand should IMO choose the grammar (if not explicitly given) at compile-time if at all possible. Earlier is better there, I suspect.

Not at all sure:

Naming things with string designators instead of symbols. I see the attraction, but this means that all rules in a grammar are public and prone to conflict, no?

If I have a grammar G1 in package BAR that specifies a rule called BAR:WHITESPACE and a G2 in FOO that specified FOO:WHITESPACE, then G3 in QUUX can use both without problems. If both rules are really called "WHITESPACE", things can get confusing pretty quickly...

[scymtym]

Thanks for the feedback. I will rebase onto new master and try to address the remaining problems.

[scymtym]

I updated the branch according to your suggestions. A detailed description can be found in the updated commit message.

In case you accept the pull request, please squash the two commits into one. If you have further feedback, just let me know.

In case #18 looks acceptable, please merge that one first and let me rebase this branch.

Many thanks in advance.

[Menschenkindlein]

I am not sure about we really have an issue here. See multiple grammars with vanilla esrap: https://gist.github.com/4655164

But if using native Common Lisp packages system is a prohibited way, and we must reimplement it, we can use something like local nicknames - local prefixes for grammars, that will allow us to use grammars with the same names for different rules.

(defgrammar #:sexp
  (:local-prefixes (#:xml "xml-")))
(in-grammar #:sexp)
(defrule :xml (and "(xml \"" :xml-xml "\")"))

(defgrammar #:xml
  (:local-prefixes (#:sexp "sexp-")))
(in-grammar #:xml)
(defrule :sexp (and "<sexp>" :sexp-sexp "</sexp>"))

P.S. IMHO error on circular dependencies IS NOT good.

[scymtym]

In the long run, I would also like to allow circular dependencies between grammars in order to support mutually recursive rules across grammars.

I omitted this ability from the proposal to reduce complexity while the proposal is in an early discussion stage. Should the proposal be accepted, I would like to add support for circular dependencies later.

[scymtym]

Further development in scymtym/esrap.