0000004: ocamlyacc and $end

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0000004

OCaml

OCaml general

public

1999-12-20 11:08

2005-12-15 15:48

Reporter

administrator

Assigned To

Priority

normal

Severity

minor

Reproducibility

always

Status

closed

Resolution

won't fix

Platform

OS Version

Product Version

Target Version

Fixed in Version

Summary

0000004: ocamlyacc and $end

Description

Full_Name: Judicael Courant
Version: 2.02
OS:
Submission from: estephe.inria.fr (128.93.11.95)
Submitted by: xleroy

(re)Bonjour,

mes étudiants font très fort. Un autre binôme a trouvé (malgré lui et
sans oser m'en parler) ce qui me semble être un bug d'ocamlyacc. En
simplifié, ça donne :

lexer.mll
----------------------------------------------------------------------
{
  open Parser
}

rule token =
parse [ '\n' '\t' ' '] { token lexbuf}
   | ['a'-'z']+ { IDENT(Lexing.lexeme lexbuf)}
   | ['0'-'9']+ { INT(int_of_string (Lexing.lexeme lexbuf))}
   | ['+'] { PLUS }
   | ['('] { PARENG }
   | [')'] { PAREND }
   | eof { FIN }

{
  let get_token l =
    let t = token l in
      (match t with
    | IDENT s -> print_string "\nIDENT:" ; print_string s; print_newline()
    | INT i -> print_string "\nINT" ; print_int i; print_newline ()
    | PLUS -> print_string "\nPLUS\n" ; flush stdout
    | FIN -> print_string "\nEOF\n" ; flush stdout
        | PARENG -> print_string "\nPARENG\n"; flush stdout
    | PAREND -> print_string "\nPAREND\n"; flush stdout);
      t
}
----------------------------------------------------------------------

parser.mly:
----------------------------------------------------------------------
%{
%}

%token <int> INT
%token <string> IDENT
%token PLUS
%token PARENG PAREND
%token FIN

%left PLUS

%start main
%type <unit>main

%%

main:

        instruction {print_string "\ninstruction\n"; flush stdout}

    ;

expr:
    /* Constantes de types simples. */
    INT
    {
        print_string "\nINT:"; print_int $1;flush stdout
    }
|expr PLUS expr
    {
      print_string "\nPlus"
    }
;

instruction:
expr { print_string "\ninstruction\n" ; flush stdout }

|IDENT PARENG PAREND { print_string "\nCall" ; flush stdout}

;
----------------------------------------------------------------------

pc87:~/tmp/test> ocamlyacc parser.mly;ocamlc -c parser.mli;ocamlc -c
parser.ml;ocamllex lexer.mll;ocamlc -c lexer.ml
8 states, 283 transitions, table size 1180 bytes
pc87:~/tmp/test>
pc87:~/tmp/test> ocaml
        Objective Caml version 2.02

#
#load "lexer.cmo";;
  #load "parser.cmo";;
# # let f s =
  let lexbuf = Lexing.from_string s in
    Parser.main Lexer.get_token lexbuf
  ;;
  val f : string -> unit = <fun>
# f "f()+3";;

IDENT:f

PARENG

PAREND

Call
instruction
- : unit = ()
# (* Ah ok : bien que la doc ne soit pas explicite là-dessus, il
semble que l'on n'échoue pas si un préfixe de la suite de token peut
être reconnu.
Essayons donc : *)

    f " 3 4 5";;

INT3

INT:3
INT4
Uncaught exception: Parsing.Parse_error
#

Pourquoi donc cette différence ?

Si on regarde l'automate donné par ocamlyacc -v on a :

----------------------------------------------------------------------
state 2
    $accept : %entry% . $end (0)

    $end accept
[..]
state 7
    expr : expr . PLUS expr (3)
    instruction : expr . (4)

    PLUS shift 9
    $end reduce 4
----------------------------------------------------------------------

je ne suis pas sûr de bien comprendre ce que représente $end. J'avais
l'impression que c'était EOF, mais alors que se passe t-il lorsque
l'on n'a pas $end dans le premier cas et ni $end ni PLUS dans le
second cas ?

BTW, le rôle particulier joué par "EOF" n'est pas documenté dans le
manuel. En particulier, on a :

# f "2+4";;

INT2

INT:2
PLUS

INT4

INT:4
Plus
EOF
Uncaught exception: Parsing.Parse_error
#

Mais si on remplace "FIN" par "EOF" dans lexer.mll et parser.mly, on a
bien :

----------------------------------------------------------------------
#
f "2+4";;

INT2

INT:2
PLUS

INT4

INT:4
Plus
EOF

instruction

instruction
- : unit = ()
#
----------------------------------------------------------------------

En fait, il serait bien

- soit de dire dans la doc qu'il faut toujours que les non-terminaux
axiomes soient constitués d'une production de la forme

x:
  y T { .. }

où T est un token

- soit de dire qu'il n'est pas nécessaire d'écrire de symbole de fin, et
  que l'analyseur engendré par ocamlyacc reconnaît le flot de tokens
  analysé jusqu'au symbole EOF (qui serait un token toujours déclaré
  implicitement par ocamlyacc).

Judicaël.
--
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/ [^]
[Computing timetable constraints..................done: 0 solution(s)]

Issue History
Date Modified	Username	Field	Change
2005-11-18 10:14	administrator	New Issue
2005-12-15 15:48	doligez	Status	acknowledged => closed
2005-12-15 15:48	doligez	Resolution	open => won't fix
2005-12-15 15:48	doligez	Description Updated
2005-12-15 15:49	doligez	Relationship added	related to 0000420

Notes
(0002991) administrator (administrator) 2003-03-13 18:28	see PR#420