jhjourdan / c11parser Goto Github PK
View Code? Open in Web Editor NEWA correct C89/C90/C99/C11/C18 parser written using Menhir and OCaml
License: Other
A correct C89/C90/C99/C11/C18 parser written using Menhir and OCaml
License: Other
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!
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
.
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
_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 | };
| ^
struct {
_Alignas(int) char x;
} a;
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.
Seems project is very active, would be nice to use modern buildsystem too.
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.
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.
See https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions
I would be particularly interested in "Statement Exprs" and "Other Builtins".
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.
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
parse
built in this repogcc -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
tests/bitfield_declaration_ambiguity.ok.c
typedef signed int T;
struct S {
unsigned T:3; // bit-field named T with type unsigned
};
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 {
| ^
typedef signed int T;
struct S {
int x;
const T:3; // anonymous bit-field with type const T
};
signed
and unsigned
cannot be used togetherunsigned signed int x;
unsigned_signed_int.c:1:10: error: both ‘signed’ and ‘unsigned’ in declaration specifiers
1 | unsigned signed int x;
typedef signed int T;
unsigned T x;
unsigned_signed_typedef.c:2:12: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘x’
2 | unsigned T x;
bitfield_declaration_ambiguity.c
?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!
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"
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.
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
.
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.
tests.t
now mentions aligned_struct_c18.c
but the file isn't committed so the test fails. (I suspect this was an oversight.
Is this in the works? :)
It seems that although you have named it whitespace_char_no_newline
here
Line 60 in a8977f2
\n
as \012
.A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.