jhjourdan / c11parser Goto Github PK

View Code? Open in Web Editor NEW

188.0 188.0 16.0 96 KB

A correct C89/C90/C99/C11/C18 parser written using Menhir and OCaml

License: Other

Makefile 2.03% OCaml 67.12% C 9.55% Yacc 17.90% Perl 3.40%

c11parser's People

Contributors

Stargazers

Watchers

Forkers

hnakamur ajinkyakulkarni kultarr pmetzger exced thvnx let-def quinzio doytsujin albertogp tiancheng-luo cshonig xpinguin smuenzel dophist zmajeedforks

c11parser's Issues

Make failed at %type<declarator> in parser_ansi_compatible.mly

Hi,
I ran make and got the following error.

$ make
ocamlbuild -menhir "menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v" main.native
Finished, 1 target (0 cached) in 00:00:00.
+ menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v --ocamlc '/usr/bin/ocamlc -w @1..49-4-9-41-44' --explain --infer parser.mly
Grammar has 127 nonterminal symbols, among which 1 start symbols.
Grammar has 97 terminal symbols.
Grammar has 305 productions.
Built an LR(0) automaton with 506 states.
The grammar is not SLR(1) -- 15 states have a conflict.
Built an LR(1) automaton with 506 states.
One shift/reduce conflict was silently solved.
Warning: one state has reduce/reduce conflicts.
Warning: 3 reduce/reduce conflicts were arbitrarily resolved.
+ menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v --external-tokens Parser --raw-depend --ocamldep '/usr/bin/ocamldep -modules' parser_ansi_compatible.mly > parser_ansi_compatible.mly.depends
File "parser_ansi_compatible.mly", line 44, characters 29-46:
Error: how is this symbol parameterized?
It is used at sorts * -> * and *.
The sort * -> * is not compatible with the sort *.
Command exited with code 1.
Compilation unsuccessful after building 14 targets (0 cached) in 00:00:01.
Makefile:16: recipe for target 'all' failed
make: *** [all] Error 10

My environment information:

$ ocaml -version
The OCaml toplevel, version 4.02.3
$ opam show menhir | grep installed-version:
   installed-version: 20160825 [system]
$ git rev-parse HEAD
9e7237e43a916bf20a917689afe8ec3d7214216a

Could you tell me how to fix it?
Thanks!

File "parser.mly", line 45, characters 15-16: Error: unexpected character(s).

While trying to verify my environment I did

==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser> ocaml --version
The OCaml toplevel, version 4.05.0
==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser> ocamlbuild --version
ocamlbuild 0.13.0
==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser> menhir --version
menhir, version 20170712
==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser> git --no-pager log -1
commit dcb5d5863db24e39e8a16eeb571a1387647a6e19 (HEAD -> master, origin/master, origin/HEAD, wips, ok)
Merge: 69bb4cb d15c40d
Author: Jacques-Henri Jourdan <[email protected]>
Date:   Wed Nov 14 15:48:27 2018 +0100

    Merge pull request #8 from waldyrious/patch-1
    
    README: add links and format code
==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser> make realclean test
rm -rf _build parse
rm -f parser.output parser.tab.c
rm -f parser.y
ocamlbuild -menhir "menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v" main.native
Finished, 1 target (0 cached) in 00:00:00.
+ menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v --raw-depend --ocamldep 'ocamldep.opt -modules' parser.mly > parser.mly.depends
File "parser.mly", line 45, characters 15-16:
Error: unexpected character(s).
Command exited with code 1.
Compilation unsuccessful after building 6 targets (0 cached) in 00:00:00.
make: *** [Makefile:34: all] Error 10
==== jnml@e5-1650:~/src/github.com/jhjourdan/C11parser>

OS: openSuse Leap 15.0 64 bit

I'd expect make realclean test to succeed and produce parser.y.

Questions about test aligned_struct_c18.c

This is tests/aligned_struct_c18.c

struct {
  _Alignas(int) char x;
};

And how it's listed in tests/tests.t

SHOULD FAIL (does not because we do not have a semantic analysis):
  $ $PARSECMD < $TESTDIR/aligned_struct_c18.c

There are some issues with this test

The file fails to parse with GCC-14 with an error that has nothing to do with _Alignas

gcc -std=c18 -fsyntax-only -Wpedantic -pedantic-errors tests/aligned_struct_c18.c

tests/aligned_struct_c18.c:3:1: error: unnamed struct/union that defines no instances
    3 | };
      | ^

Indeed gcc successfully parses the following modified test

struct {
  _Alignas(int) char x;
} a;

So I don't get the purpose of this test - was it motivated by a limitation in C11 that was corrected with DR 444 - https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_444.htm?

there is no way in the syntax to apply such an alignment to a member

If that's the case then why would semantic analysis be needed for _Alignas to not be recognized inside a struct since the limitation was purely syntactical.

Switch to dune build system

Seems project is very active, would be nice to use modern buildsystem too.

Someone should check conformance with C18 draft n2176

C18 is out, and it's only a set of technical corrections to C11 with no substantive changes. The final draft document, N2176, is located at:
http://www.open-std.org/jtc1/sc22/wg14/www/abq/c17_updated_proposed_fdis.pdf

Someone should, at some point, check that there are no changes that would substantively alter the parser.

tests have a minor failure

I note that the README should probably mention that one needs cram to run the tests.
make test results in this minor failure:

ocamlbuild -menhir "menhir --no-stdlib --unused-token IMAGINARY -lg 1 -la 1 -v" main.native
mv main.native parse
cram tests/tests.t
!
--- tests/tests.t
+++ tests/tests.t.err
@@ -30,7 +30,7 @@
   $ $PARSECMD < $TESTDIR/dangling_else.c
 SHOULD FAIL:
   $ $PARSECMD < $TESTDIR/dangling_else_misleading.fail.c
-  Fatal error: exception Parser.Basics.Error
+  Fatal error: exception Parser.MenhirBasics.Error
   [2]
   $ $PARSECMD < $TESTDIR/dangling_else_lookahead.c
   $ $PARSECMD < $TESTDIR/dangling_else_lookahead.if.c

# Ran 1 tests, 0 skipped, 1 failed.

Document which, if any, common gcc and clang extensions are supported

See https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions

I would be particularly interested in "Statement Exprs" and "Other Builtins".

function-decls.c uses sizeof on function type (constraint error)

I noticed that function-decls.c contains the following line:

X = sizeof(void (*(int arga, void (*argb)(double Y)))(void* Z));

Unless I'm mistaken, the typename void (*(int arga, void (*argb)(double Y)))(void* Z) specifies a function type with arguments int and pointer to function with argument double returning void, returning pointer to function with argument pointer to void returning void.

This is a function type, but C17 6.5.3.4p1 says (in the constraints section)

The sizeof operator shall not be applied to an expression that has function type or an incomplete
type, to the parenthesized name of such a type, or to an expression that designates a bit-field member.

gcc correctly produces a warning when compiling with -Wpedantic:

$ gcc -std=c17 -Wpedantic -c function-decls.c
function-decls.c: In function 'foo':
function-decls.c:5:14: warning: invalid application of 'sizeof' to a function type [-Wpointer-arith]
    5 |   X = sizeof(void (*(int arga, void (*argb)(double Y)))(void* Z));
      |              ^~~~

I know these tests are mainly about syntax, but since the repository states that these are all valid C18 fragments, I think the test should be tweaked to avoid the constraint error.

Questions about test bitfield_declaration_ambiguity.c

This is tests/bitfield_declaration_ambiguity.c

1.  // bitfield_declaration_ambiguity.c
2.  typedef signed int T;
3.  struct S {
4.    unsigned T:3; // bit-field named T with type unsigned
5.    const T:3;    // anonymous bit-field with type const T
6.  };

And how it's listed in tests/tests.t

SHOULD FAIL:
  $ $PARSECMD < $TESTDIR/bitfield_declaration_ambiguity.c

Some comments on this test

The test does not fail with GCC-14 nor with parse built in this repo

gcc -std=c18 -fsyntax-only -Wpedantic -pedantic-errors tests/bitfield_declaration_ambiguity.c

echo $?
0

parse -std c11 -atomic-permissive-syntax <tests/bitfield_declaration_ambiguity.c

lexer: return INT
lexer: return VARIABLE
lexer: return VARIABLE
lexer: return TYPE
lexer: return TYPE
translation_unit_file: external_declaration EOF
translation_unit_file: external_declaration translation_unit_file

echo $?
0

The test still passes with line 5 removed - which is essentially tests/bitfield_declaration_ambiguity.ok.c

typedef signed int T;
struct S {
  unsigned T:3; // bit-field named T with type unsigned
};

But fails with line 4 removed for nothing to do with bitfields - essentially tests/bitfield_declaration_ambiguity.fail.c

typedef signed int T;
struct S {
  const T:3;    // anonymous bit-field with type const T
};

bitfield_declaration_ambiguity.2.c:2:8: error: struct has no named members [-Wpedantic]
    2 | struct S {
      |        ^

Adding a named field makes it pass

typedef signed int T;
struct S {
  int x;
  const T:3;    // anonymous bit-field with type const T
};

Normally signed and unsigned cannot be used together

unsigned signed int x;

unsigned_signed_int.c:1:10: error: both ‘signed’ and ‘unsigned’ in declaration specifiers
    1 | unsigned signed int x;

Even with typedef but the error is not informative

typedef signed int T;
unsigned T x;

unsigned_signed_typedef.c:2:12: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘x’
    2 | unsigned T x;

What is the purpose of test bitfield_declaration_ambiguity.c?

Package this as a library?

I've long been looking for an ocaml equivalent of the parsing and AST parts of Haskell's excellent Language.C module, so this package looks very interesting to me. C.f. http://hackage.haskell.org/package/language-c-0.8.2/docs/Language-C-Syntax-AST.html

However, I'm confused as to how this code is supposed to be used. The readme suggests modifying the parser actions, but doesn't this mean every user has to maintain their own modified copy of the parser?

Thanks!

Grammar railroad diagram

I've done a experimental tool to convert bison grammars to a kind of EBNF understood by https://www.bottlecaps.de/rr/ui to generate railroad diagrams see bellow the converted parser.mly and with some hand made changes to allow view it at https://www.bottlecaps.de/rr/ui the order of the rules could be changed to a better view of the railroad diagrams. Copy and paste the EBNF bellow on https://www.bottlecaps.de/rr/ui tab Edit Grammar then switch to the tab View Diagram.

/*
From https://github.com/jhjourdan/C11parser/blob/master/parser.mly
*/

translation_unit_file ::=  external_declaration translation_unit_file | external_declaration EOF
external_declaration ::=  function_definition | declaration
function_definition ::=  function_definition1 declaration_list? compound_statement
declaration_list ::=  declaration | declaration_list declaration
function_definition1 ::=  declaration_specifiers declarator_varname
jump_statement ::=  "goto" general_identifier ";" | "continue" ";" | "break" ";" | "return" expression? ";"
iteration_statement ::=  "while" "(" expression ")" scoped | "do" scoped "while" "(" expression ")" ";" | "for" "(" expression? ";" expression? ";" expression? ")" scoped | "for" "(" declaration expression? ";" expression? ")" scoped
selection_statement ::=  "if" "(" expression ")" scoped "else" scoped | "if" "(" expression ")" scoped | "switch" "(" expression ")" scoped
expression_statement ::=  expression? ";"
block_item ::=  declaration | statement
block_item_list ::=  block_item_list? block_item
compound_statement ::=  "{" block_item_list? "}"
labeled_statement ::=  general_identifier ":" statement | "case" constant_expression ":" statement | "default" ":" statement
statement ::=  labeled_statement | scoped | expression_statement | scoped | scoped | jump_statement
static_assert_declaration ::=  "_Static_assert" "(" constant_expression "," STRING_LITERAL ")" ";"
designator ::=  "[" constant_expression "]" | "." general_identifier
designator_list ::=  designator_list? designator
designation ::=  designator_list "="
initializer_list ::=  designation? c_initializer | initializer_list "," designation? c_initializer
c_initializer ::=  assignment_expression | "{" initializer_list ","? "}"
direct_abstract_declarator ::=  "(" save_context abstract_declarator ")" | direct_abstract_declarator? "[" ioption assignment_expression? "]" | direct_abstract_declarator? "[" "static" type_qualifier_list? assignment_expression "]" | direct_abstract_declarator? "[" type_qualifier_list "static" assignment_expression "]" | direct_abstract_declarator? "[" "*" "]" | ioption "(" scoped? ")"
abstract_declarator ::=  pointer | ioption direct_abstract_declarator
type_name ::=  specifier_qualifier_list abstract_declarator?
identifier_list ::=  var_name | identifier_list "," var_name
parameter_declaration ::=  declaration_specifiers declarator_varname | declaration_specifiers abstract_declarator?
parameter_list ::=  parameter_declaration | parameter_list "," parameter_declaration
parameter_type_list ::=  parameter_list option save_context
type_qualifier_list ::=  type_qualifier_list? type_qualifier
pointer ::=  "*" type_qualifier_list? pointer?
direct_declarator ::=  general_identifier | "(" save_context declarator ")" | direct_declarator "[" type_qualifier_list? assignment_expression? "]" | direct_declarator "[" "static" type_qualifier_list? assignment_expression "]" | direct_declarator "[" type_qualifier_list "static" assignment_expression "]" | direct_declarator "[" type_qualifier_list? "*" "]" | direct_declarator "(" scoped ")" | direct_declarator "(" save_context identifier_list? ")"
declarator ::=  ioption direct_declarator
alignment_specifier ::=  "_Alignas" "(" type_name ")" | "_Alignas" "(" constant_expression ")"
function_specifier ::=  "inline" | "_Noreturn"
type_qualifier ::=  "const" | "restrict" | "volatile" | "_Atomic"
atomic_type_specifier ::=  "_Atomic" "(" type_name ")" | "_Atomic" ATOMIC_LPAREN type_name ")"
enumeration_constant ::=  general_identifier
enumerator ::=  enumeration_constant | enumeration_constant "=" constant_expression
enumerator_list ::=  enumerator | enumerator_list "," enumerator
enum_specifier ::=  "enum" general_identifier? "{" enumerator_list ","? "}" | "enum" general_identifier
struct_declarator ::=  declarator | declarator? ":" constant_expression
struct_declarator_list ::=  struct_declarator | struct_declarator_list "," struct_declarator
specifier_qualifier_list ::=  list_eq1 | list_ge1
struct_declaration ::=  specifier_qualifier_list struct_declarator_list? ";" | static_assert_declaration
struct_declaration_list ::=  struct_declaration | struct_declaration_list struct_declaration
struct_or_union ::=  "struct" | "union"
struct_or_union_specifier ::=  struct_or_union general_identifier? "{" struct_declaration_list "}" | struct_or_union general_identifier
type_specifier_unique ::=  "void" | "_Bool" | atomic_type_specifier | struct_or_union_specifier | enum_specifier | typedef_name_spec
type_specifier_nonunique ::=  "char" | "short" | "int" | "long" | "float" | "double" | "signed" | "unsigned" | "_Complex"
storage_class_specifier ::=  "extern" | "static" | "_Thread_local" | "auto" | "register"
init_declarator ::=  declarator | declarator "=" c_initializer
init_declarator_list ::=  init_declarator | init_declarator_list "," init_declarator
declaration_specifiers_typedef ::=  list_eq1_eq1 | list_eq1_ge1
declaration_specifiers ::=  list_eq1 | list_ge1
declaration_specifier ::=  storage_class_specifier | type_qualifier | function_specifier | alignment_specifier
declaration ::=  declaration_specifiers init_declarator_list? ";" | declaration_specifiers_typedef init_declarator_list? ";" | static_assert_declaration
constant_expression ::=  conditional_expression
expression ::=  assignment_expression | expression "," assignment_expression
assignment_operator ::=  "=" | "*=" | "/=" | "%=" | "+=" | "-=" | "<<=" | ">>=" | "&=" | "^=" | "|="
assignment_expression ::=  conditional_expression | unary_expression assignment_operator assignment_expression
conditional_expression ::=  logical_or_expression | logical_or_expression "?" expression ":" conditional_expression
logical_or_expression ::=  logical_and_expression | logical_or_expression "||" logical_and_expression
logical_and_expression ::=  inclusive_or_expression | logical_and_expression "&&" inclusive_or_expression
inclusive_or_expression ::=  exclusive_or_expression | inclusive_or_expression "|" exclusive_or_expression
exclusive_or_expression ::=  and_expression | exclusive_or_expression "^" and_expression
and_expression ::=  equality_expression | and_expression "&" equality_expression
equality_expression ::=  relational_expression | equality_expression equality_operator relational_expression
equality_operator ::=  "==" | "!="
relational_expression ::=  shift_expression | relational_expression relational_operator shift_expression
relational_operator ::=  "<" | ">" | "<=" | ">="
shift_expression ::=  additive_expression | shift_expression shift_operator additive_expression
shift_operator ::=  "<<" | ">>"
additive_expression ::=  multiplicative_expression | additive_expression additive_operator multiplicative_expression
additive_operator ::=  "+" | "-"
multiplicative_expression ::=  cast_expression | multiplicative_expression multiplicative_operator cast_expression
multiplicative_operator ::=  "*" | "/" | "%"
cast_expression ::=  unary_expression | "(" type_name ")" cast_expression
unary_operator ::=  "&" | "*" | "+" | "-" | "~" | "!"
unary_expression ::=  postfix_expression | "++" unary_expression | "--" unary_expression | unary_operator cast_expression | "sizeof" unary_expression | "sizeof" "(" type_name ")" | "_Alignof" "(" type_name ")"
argument_expression_list ::=  assignment_expression | argument_expression_list "," assignment_expression
postfix_expression ::=  primary_expression | postfix_expression "[" expression "]" | postfix_expression "(" argument_expression_list? ")" | postfix_expression "." general_identifier | postfix_expression "->" general_identifier | postfix_expression "++" | postfix_expression "--" | "(" type_name ")" "{" initializer_list ","? "}"
generic_association ::=  type_name ":" assignment_expression | "default" ":" assignment_expression
generic_assoc_list ::=  generic_association | generic_assoc_list "," generic_association
generic_selection ::=  "_Generic" "(" assignment_expression "," generic_assoc_list ")"
primary_expression ::=  var_name | CONSTANT | STRING_LITERAL | "(" expression ")" | generic_selection
declarator_typedefname ::=  declarator
declarator_varname ::=  declarator
scoped ::=  save_context X
save_context ::=  /* empty */
general_identifier ::=  typedef_name | var_name
typedef_name_spec ::=  typedef_name
var_name ::=  NAME VARIABLE
typedef_name ::=  NAME TYPE
list_eq1_ge1 ::=  A list_ge1 | B list_eq1 | B list_eq1_ge1 | C list_eq1_ge1
list_eq1_eq1 ::=  A list_eq1 | B list_eq1 | C list_eq1_eq1
list_ge1 ::=  A B* | A list_ge1 | B list_ge1
list_eq1 ::=  A B* | B list_eq1
list ::=  /* empty */ | X list
option ::=  ioption
ioption ::=  /* empty */ | X

// Tokens

ELLIPSIS ::= "..."
ADD_ASSIGN ::= "+="
SUB_ASSIGN ::= "-="
MUL_ASSIGN ::= "*="
DIV_ASSIGN ::= "/="
MOD_ASSIGN ::= "%="
OR_ASSIGN ::= "|="
AND_ASSIGN ::= "&="
XOR_ASSIGN ::= "^="
LEFT_ASSIGN ::= "<<="
RIGHT_ASSIGN ::= ">>="
LEFT ::= "<<"
RIGHT ::= ">>"
EQEQ ::= "=="
NEQ ::= "!="
LEQ ::= "<="
GEQ ::= ">="
EQ ::= "="
LT ::= "<"
GT ::= ">"
INC ::= "++"
DEC ::= "--"
PTR ::= "->"
PLUS ::= "+"
MINUS ::= "-"
STAR ::= "*"
SLASH ::= "/"
PERCENT ::= "%"
BANG ::= "!"
ANDAND ::= "&&"
BARBAR ::= "||"
AND ::= "&"
BAR ::= "|"
HAT ::= "^"
QUESTION ::= "?"
COLON ::= ":"
TILDE ::= "~"
LBRACE ::= "{"|"<%"
RBRACE ::= "}"|"%>"
LBRACK ::= "["|"<:"
RBRACK ::= "]"|":>"
LPAREN ::= "("
RPAREN ::= ")"
SEMICOLON ::= ";"
COMMA ::= ","
DOT ::= "."
ALIGNAS ::= "_Alignas"
ALIGNOF ::= "_Alignof"
ATOMIC ::= "_Atomic"
BOOL ::= "_Bool"
COMPLEX ::= "_Complex"
GENERIC ::= "_Generic"
IMAGINARY ::= "_Imaginary"
NORETURN ::= "_Noreturn"
STATIC_ASSERT ::= "_Static_assert"
THREAD_LOCAL ::= "_Thread_local"
AUTO ::= "auto"
BREAK ::= "break"
CASE ::= "case"
CHAR ::= "char"
CONST ::= "const"
CONTINUE ::= "continue"
DEFAULT ::= "default"
DO ::= "do"
DOUBLE ::= "double"
ELSE ::= "else"
ENUM ::= "enum"
EXTERN ::= "extern"
FLOAT ::= "float"
FOR ::= "for"
GOTO ::= "goto"
IF ::= "if"
INLINE ::= "inline"
INT ::= "int"
LONG ::= "long"
REGISTER ::= "register"
RESTRICT ::= "restrict"
RETURN ::= "return"
SHORT ::= "short"
SIGNED ::= "signed"
SIZEOF ::= "sizeof"
STATIC ::= "static"
STRUCT ::= "struct"
SWITCH ::= "switch"
TYPEDEF ::= "typedef"
UNION ::= "union"
UNSIGNED ::= "unsigned"
VOID ::= "void"
VOLATILE ::= "volatile"
WHILE ::= "while"

Incorrect lexing of character literals

According to 6.4.4.4, we have

character-constant:
' c-char-sequence '

c-char-sequence:
c-char
c-char-sequence c-char

However, the lexer currently accepts '' as an empty char constant.

Lexer recognizes "alignof"

The lexer recognizes "alignof", see:

      ("_Alignof", ALIGNOF);
 ...
      ("alignof", ALIGNOF);

I believe alignof is a macro defined in <stdalign.h> and is not a language reserved word. It should probably not be recognized by the lexer as an alias for _Alignof.

Abstract syntax trees & backend for C11parser

The libfirm library (on GitHub: https://github.com/libfirm/libfirm) provides all the basics required for processing abstract syntax trees, carrying out a range of standard optimizations, and targeting for a range of back ends.

When combined with a suitable parser, it may suffice to serve as a drop-in replacement for GCC's implementation of C11 or C18.

A companion front end, cparser, is also provided (on GitHub: https://github.com/libfirm/cparser) that contains suitable abstract syntax trees for C11, but a recursive-descent parser. It may be possible to adapt its tree-construction, tree-walking and semantic analysis routines into your parser - thereby making possible a larger suite of regression tests against a larger codebase (including the parser itself).

A note has also been sent to cparser informing the developers of your regression tests under "tests" and your lexer and parser. The two sets of projects, C11parser and cparser, should actually be combined.

Line 60 in a8977f2

let whitespace_char_no_newline = [' ' '\t' '\012' '\r']

in reality you are including the \n as \012.