Home / Browse / CEDET / Mail / Archive

CEDET

Email Archive: cedet-semantic (read-only)

[cedet-semantic] broken self-reference?

From: Joe Corneli <jcorneli@ma...> - 2004-05-10 17:16

I already posted a question along these lines, but perhaps the
following example files will make the question more clear (and so,
hopefully, easier to answer).

The two files are identical except that in the first one, the
productions of `expr' do *not* refer to `expr', and in the second
one, one of them does.

The second one is broken... when I use it to generate my parser,
the text

 /* problem */
 "abc" = "ced"

is not recognized.  But with the first version, there is no problem.

Could someone please explain why this is and how to work around it?
The parsing system that I'm working my way up to is full of
self-reference!

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
;;; simple.wy -- LALR grammar for (simplified) Tiger

%package simple-wy

;; Not really necessary, as it is the default start symbol
%start expr

%type  <symbol>
%token <symbol> symbol "[A-Za-z][_A-Za-z0-9]*"

%type  <string>
%token <string> STRING_LITERAL

%type  <keyword>
%keyword EQ                      "="

%%

;; For use with Semantic, must return valid semantic tags!
expr
  : ;; Empty
  | STRING_LITERAL
    (TAG "string" 'expr :value $1)
  | STRING_LITERAL EQ STRING_LITERAL
    (TAG "expr eq" 'expr :value (concat "(equal " 
                                        $1 
                                        " " 
                                        $3 
                                        ")"))
 ;

%%

(define-lex simple-lexer
  "Simple lexical analyzer."
  semantic-lex-ignore-whitespace
  semantic-lex-ignore-newline
  semantic-lex-ignore-comments
  ;;;; Auto-generated analyzers.
  simple-wy--<keyword>-keyword-analyzer
  ;; From the documentation string for `semantic-lex-tokens':
  ;; "Always add this analyzer *after* `semantic-lex-number', or other
  ;; analyzers that match its regular expression." (my emphasis)
  simple-wy--<symbol>-regexp-analyzer
  simple-wy--<string>-sexp-analyzer
  ;;;;
  semantic-lex-default-action)

;;; simple.wy ends here

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

;;; simple.wy -- LALR grammar for (simplified) Tiger

%package simple-wy

;; Not really necessary, as it is the default start symbol
%start expr

%type  <symbol>
%token <symbol> symbol "[A-Za-z][_A-Za-z0-9]*"

%type  <string>
%token <string> STRING_LITERAL

%type  <keyword>
%keyword EQ                      "="

%%

;; For use with Semantic, must return valid semantic tags!
expr
  : ;; Empty
  | STRING_LITERAL
    (TAG "string" 'expr :value $1)
 ;; refering to expr seems to make this break, why?
  | expr EQ expr
    (TAG "expr eq" 'expr :value (concat "(equal " 
                                        $1 
                                        " " 
                                        $3 
                                        ")"))
 ;

%%

(define-lex simple-lexer
  "Simple lexical analyzer."
  semantic-lex-ignore-whitespace
  semantic-lex-ignore-newline
  semantic-lex-ignore-comments
  ;;;; Auto-generated analyzers.
  simple-wy--<keyword>-keyword-analyzer
  ;; From the documentation string for `semantic-lex-tokens':
  ;; "Always add this analyzer *after* `semantic-lex-number', or other
  ;; analyzers that match its regular expression." (my emphasis)
  simple-wy--<symbol>-regexp-analyzer
  simple-wy--<string>-sexp-analyzer
  ;;;;
  semantic-lex-default-action)

;;; simple.wy ends here

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

;;; simple-mode.el -- major mode for a simple language

;;; Semantic parsing support

(require 'semantic-wisent)
(require 'simple-wy)

;;;###autoload
(defun semantic-default-simple-setup ()
  "Set up a buffer for semantic parsing of a SIMPLE language."
  ;; Do some useful things.
  (setq semantic-ignore-comments t)
  ;; Install the parser
  (simple-wy--install-parser)
  ;; Setup the lexer
  (setq semantic-lex-analyzer 'simple-lexer
        ;; Do a full depth lexical analysis.
        semantic-lex-depth nil))

;;;###autoload
(add-hook 'simple-mode-hook 'semantic-default-simple-setup)

;;; post parser processing

(defun clean-up-parser-output ()
  (interactive)
  (set-buffer (get-buffer "*Parser Output*"))
  (flush-lines "overlay")
  (flush-lines "expr")
;;  (flush-lines "\"expr\" expr")
  (goto-char (point-min))
  (replace-regexp "  (:value \"\\|\")$" "")
  (goto-char (point-min))
  (replace-regexp "\\\\\"" "\""))

(defun novinate ()
  (interactive)
  (bovinate)
  (clean-up-parser-output)
  (other-window 1))

;;; simple major mode

(defvar simple-mode-syntax-table
  (let ((table (make-syntax-table (standard-syntax-table))))
    (modify-syntax-entry ?\+ "."     table) ;; Operator PLUS
    (modify-syntax-entry ?\- "."     table) ;; Operator MINUS
    ;; also deals with comments
    (modify-syntax-entry ?\* ". 23"  table) ;; Operator MULT
    (modify-syntax-entry ?\/ ". 14"  table) ;; Operator DIV
    ;; deal with brackets
    (modify-syntax-entry ?\( "()"    table)
    (modify-syntax-entry ?\{ "(}"    table)
    (modify-syntax-entry ?\[ "(]"    table)
    (modify-syntax-entry ?\) ")("    table)
    (modify-syntax-entry ?\} "){"    table)
    (modify-syntax-entry ?\] ")["    table)
    table)
  "Syntax table used in simple mode buffers.
Define operators as punctuations.")

;;;###autoload
(define-derived-mode simple-mode fundamental-mode "simple"
  (setq comment-start-skip "/\\*+ *"))

;;;###autoload
(add-to-list 'auto-mode-alist '("\\.simple\\'" . simple-mode))

;(defvar simple-mode-hook nil)

(provide 'simple-mode)

;;; simple-mode.el ends here

Thread View

Thread	Author	Date
[cedet-semantic] broken self-reference?	Joe Corneli <jcorneli@ma...>

Re: [cedet-semantic] broken self-reference?

From: David Ponce <david.ponce@wa...> - 2004-05-10 19:20

Hi Joe,

 > I already posted a question along these lines, but perhaps the
 > following example files will make the question more clear (and so,
 > hopefully, easier to answer).

I am sorry for not replying to your previous post more quickly!

[...]
I can see two problems in your grammar:

1- there is a shift/reduce conflict on

     state 4

         expr  ->  expr . EQ expr   (rule 3)
         expr  ->  expr EQ expr .   (rule 3)

         EQ  shift, and go to state 3

         EQ  [reduce using rule 3 (expr)]
         $default    reduce using rule 3 (expr)

___ To obtain the LALR grammar compiler detailed report, on the
"Grammar" menu, click on "LALR Compiler Verbose".  Reports will be
appended in the "*wisent-log*" buffer. ___

It means that when the EQ lookahead token is encountered, the parser
will shift it on its stack, and continue with the next token.  I guess
this is not what you want, which is probably to reduce the 'expr' on
left side first, then continue with EQ.  This is a typical precedence
conflict that can be solved in that case with a "%left EQ" statement,
which indicates to reduce 'expr' when EQ is encountered:

[...]
 > %type  <keyword>
 > %keyword EQ    "="
   %left    EQ    ;; Resolve S/R conflict in favor of reduce.

Anyway, I recommend you to read the Bison's manual which will give you
a good introduction to LALR grammar concepts, and conflicts and how to
solve them ;-)

2- There is a probably a bug in the following TAG expression:

[...]
 >   | expr EQ expr
 >     (TAG "expr eq" 'expr :value (concat "(equal "
 >                                         $1
 >                                         " "
 >                                         $3
 >                                         ")"))

Which will fail on `concat', because $1 and $2 aren't strings but
semantic tags!  This one should work better:

     (TAG "expr eq" 'expr :value (format "(equal %s %s)" $1 $3))

Finally, does it make sense that 'expr' can be empty?

Perhaps you meant something like the following?

------------------------------------------------
%start expression

%type  <symbol>
%token <symbol> symbol "[A-Za-z][_A-Za-z0-9]*"

%type  <string>
%token <string> STRING_LITERAL

%type  <keyword>
%keyword EQ     "="
%left    EQ     ;; Resolve S/R conflict in favor of reduce.

%%

;; For use with Semantic, must return valid semantic tags!
expression
   : ;;Empty
   | expr
     (TAG "expr" 'expr :value $1)
   ;

expr
   : symbol
   | STRING_LITERAL
   | expr EQ expr
     (list 'EQ $1 $3)
  ;

%%
------------------------------------------------

I tried the above grammar with this small example:

a = "c"

"a" = b

"a" = "b"

a = b

a

"b"

And M-x bovinate displayed:

(("expr" expr
   (:value
    (EQ "a" "\"c\""))
   nil #<overlay from 1 to 8 in test.simple>)
  ("expr" expr
   (:value
    (EQ "\"a\"" "b"))
   nil #<overlay from 10 to 17 in test.simple>)
  ("expr" expr
   (:value
    (EQ "\"a\"" "\"b\""))
   nil #<overlay from 19 to 28 in test.simple>)
  ("expr" expr
   (:value
    (EQ "a" "b"))
   nil #<overlay from 30 to 35 in test.simple>)
  ("expr" expr
   (:value "a")
   nil #<overlay from 37 to 38 in test.simple>)
  ("expr" expr
   (:value "\"b\"")
   nil #<overlay from 40 to 43 in test.simple>))

Hope I helped.  Good luck!
David

Re: [cedet-semantic] broken self-reference?

From: Joe Corneli <jcorneli@ma...> - 2004-05-10 20:24

___ To obtain the LALR grammar compiler detailed report, on the
   "Grammar" menu, click on "LALR Compiler Verbose".  Reports will be
   appended in the "*wisent-log*" buffer. ___

Thanks, that should be very helpful.

   conflict that can be solved in that case with a "%left EQ"
   statement, which indicates to reduce 'expr' when EQ is
   encountered

I can confirm that this works for me, but I feel a little uptight
about putting this precedence in since the spec I'm working from
says:

 "The +, -, *, and / operators are left associative. The comparison
 operators do not associate, e.g., a=b=c is erroneous, but a=(b=c)
 is legal."

Setting %left EQ doesn't trigger an error in the a=b=c
case... rather the opposite.  I wonder how I might make "expr EQ
expr" work but "expr EQ expr EQ expr" fail.

   ... will fail on `concat', because $1 and $2 aren't strings but
   semantic tags!  This one should work better:

	(TAG "expr eq" 'expr :value (format "(equal %s %s)" $1 $3))

Yes, that is better... it works! I revised that a little further to
this:

    (TAG "expr eq" 'expr :value (format "(equal %s %s)" 
                                        (car
                                         (cdaddr $1)) 
                                        (car
                                         (cdaddr $3)) ))

Where the (car (cdaddr ...) is meant to extract the :value
parameter.

   Finally, does it make sense that 'expr' can be empty?

Good question... probably not when we talk about "expr EQ expr" --

   Perhaps you meant something like the following?

   expression
      : ;;Empty
      | expr
	(TAG "expr" 'expr :value $1)
      ;

   expr
      : symbol
      | STRING_LITERAL
      | expr EQ expr
	(list 'EQ $1 $3)
     ;

Yes, that is more like it!  Thanks.  I guess that in general only
the top-level object needs to return a semantic TAG and other levels
can return ELISP forms?