Is this correct grammar definition of Backus-Naur form?

Question

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move forward due to some endless loops and I think the definition might be wrong.

This is the full definition of "Simple C Language" grammar I was given:

[1] Program = {Declaration | FunctionDefinition}.

[2] Declaration = DeclarationSpecifier [Declarator] ';'.

[3] DeclarationSpecifier = ['typedef' | 'static'] TypeSpecifier.

[4] TypeSpecifier = 'void' | 'char' | 'bool' | 'short' | 'int' | 'long' | 'double' | 'signed' | 'unsigned' | StructOrUnionSpecifier | EnumSpecifier | TypeName.

[5] StructOrUnionSpecifier = ('struct' | 'union') [Ident] '{' {StructDeclaration} '}'.

[6] StructDeclaration = TypeSpecifier Declarator {',' Declarator} ';'.

[7] EnumSpecifier = 'enum' [Ident] '{' Enumerator {',' Enumerator} '}'

[8] Enumerator = Ident ['=' ConstantExpression].

[9] Declarator = {'*'} DirectDeclarator.

[10] DirectDeclarator = Ident | '(' Declarator ')' | DirectDeclarator ( '[' [ConstantExpression] ']' | '(' [ParameterTypeList] | [Ident {',' Ident}] ')' ).

[11] ParameterTypeList = ParameterDeclaration {',' ParameterDeclaration}.

[12] ParameterDeclaration = DeclarationSpecifier [Declarator | AbstractDeclarator].

[13] TypeName = TypeSpecifier [AbstractDeclarator].

[14] AbstractDeclarator = {'*'} DirectAbstractDeclarator.

[15] DirectAbstractDeclarator = '(' AbstractDeclarator ')' | [DirectAbstractDeclarator] ( '[' [ConstantExpression] ']' | '(' [ParameterTypeList] ')' ).

[16] FunctionDefinition = [DeclarationSpecifier] Declarator {Declaration} CompoundStatement.

[17] Expression = AssignmentExpression {',' AssignmentExpression}.

[18] ConstantExpression = ConditionalExpression.

[19] AssignmentExpression = ConditionalExpression | UnaryExpression ('=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<=' | '>>=' | '&=' | '^=' | '|=') AssignmentExpression.

[20] ConditionalExpression = LogicalORExpression | LogicalORExpression '?' Expression ':' ConditionalExpression.

[21] LogicalORExpression = LogicalANDExpression {'||' LogicalANDExpression}.

[22] LogicalANDExpression = InclusiveORExpression {'&&' InclusiveORExpression}.

[23] InclusiveORExpression = ExclusiveORExpression {'|' ExclusiveORExpression}.

[24] ExclusiveORExpression = ANDExpression {'^' ANDExpression}.

[25] ANDExpression = EqualityExpression {'&' EqualityExpression}.

[26] EqualityExpression = RelationalExpression ('==' | '!=') RelationalExpression.

[27] RelationalExpression = ShiftExpression {('<' | '>' | '<=' | '>=') ShiftExpression}.

[28] ShiftExpression = AdditiveExpression {('<<' | '>>') AdditiveExpression}.

[29] AdditiveExpression = MultiplicativeExpression {('+' | '-') MultiplicativeExpression}.

[30] MultiplicativeExpression = CastExpression {('*' | '/' | '%') CastExpression}.

[31] CastExpression = {'(' TypeName ')'} UnaryExpression.

[32] UnaryExpression = PostfixExpression | ('++' | '--') UnaryExpression | ('&' | '*' | '-' | '~' | '!') CastExpression.

[33] PostfixExpression = PrimaryExpression | PostfixExpression '[' Expression ']' | PostfixExpression '(' [AssignmentExpression {',' AssignmentExpression}] ')' | PostfixExpression '.' Ident | PostfixExpression '->' Ident | PostfixExpression ('++' | '--').

[34] PrimaryExpression = Ident | Number | String | '(' Expression ')'.

[35] Statement = LabeledStatement | CompoundStatement | ExpressionStatement | SelectionStatement | IterationStatement | JumpStatement.

[36] LabeledStatement = 'case' ConstantExpression ':' Statement | 'default' ':' Statement.

[37] CompoundStatement = '{' {[Declaration] [Statement]} '}'.

[38] ExpressionStatement = [Expression] ';'.

[39] SelectionStatement = 'if' '(' Expression ')' Statement ['else' Statement] | 'switch' '(' Expression ')' Statement.

[40] IterationStatement = 'while' '(' Expression ')' Statement | 'do' Statement 'while' '(' Expression ')' ';' | 'for' '(' ExpressionStatement ExpressionStatement [Expression] ')' Statement.

[41] JumpStatement = 'continue' ';' | 'break' ';' | 'return' [Expression] ';'.

There is a high possibility that I am wrong and misunderstanding something but isn't TypeSpecifier = TypeName and TypeName = TypeSpecifier leading to some endless loop?

To my understanding, this definition means that a TypeSpecifier can be TypeName which is also TypeSpecifier and if we give them some example value like 'a' for TypeSpecifier and 'b' for TypeName then ababababab..abab is valid. Am I wrong?

Answer 1

As a side note, that grammar is not written in BNF. Rather, it is written in one of many dialects of "extended" BNF, which includes repetition and optionality operators ({ … } and [ … ]). BNF only has simple productions. However, the repetition and optional components can be macro-expanded into BNF (using a newly-created non-terminal), and the "extended BNF" is generally considered easier to read. It also corresponds directly to the code in top-down parsers, which may well be the type of parser you are being asked to write.

A context-free grammar can certainly include recursion, even indirect left recursion as exhibited by the grammar in this question. But left recursion does create a problem for a top-down parser, precisely of the nature you suggest: the top-down parser goes into an endless loop adding predictions. Bottom-up parsers do not have this problem because they recognise productions when the production is complete rather than having to predict it before it starts.

However, the grammar as written is not correct, because it does not allow the use of type aliases created with a typedef declaration:

typedef struct A { int a; } MyTypeName;
MyTypeName b;

Although the grammar will have no problem with the first line above, it will not be able to parse the second one because TypeSpecifier does not have an alternative which allows a single identifier.

The standard C grammar defines type-specifier as follows:

type-specifier:
  void
  char
  short
  int
  long
  float
  double
  signed
  unsigned
  _Bool
  _Complex
  atomic-type-specifier
  struct-or-union-specifier
  enum-specifier
  typedef-name
 

That's very similar to your grammar with the addition of a few primitives and the atomic type marker, but the last line is slightly but significantly different. This suggests that there is a typo in your grammar. I'd suggest you double check with whoever gave you the assignment.

As a note, typedef-name is just an identifier, but not any identifier; it must be an identifier previously declared as a type alias ("typedef"). That restriction cannot be expressed in a context-free grammar, and is one of the little challenges involved in writing a C parser.

If you make the change I suggest, you might run into another issue. The standard C grammar defines declaration as follows (condensed into EBNF, which the C standard doesn't use):

declaration:
  { declaration-specifier } [ init-declarator-list ] ;

which differs from your grammar because your grammar's definition of Declaration doesn't allow multiple DeclarationSpecifier. However, the (possibly accidental) recursion in TypeSpecifier in effect turns TypeSpecifier into a list, thus allowing

unsigned char uch;

However, the fact that TypeSpecifier is a list means that it will also accept things like

int double number;
unsigned struct MyStruct u;

which are not meaningful.

It's possible that the C subset you're expected to write a parser for doesn't include short char or long double, in which case the lack of repetition won't be a problem. If you do need to handle compound type names, you'll need a rather longer list of valid type names. (The standard C grammar does allow meaningless combinations of declaration-specifier, but the text of the standard limits the possible combinations. I think the authors of the standard concluded that it would be far too complicated to try to write the restrictions in BNF, and that it would be easier both for presentation and for implementation to do the check after the parse is complete.)

Answer 2

The 'endless loop' is not a problem. Remember that there are many productions possible. A word is accepted by the grammar if there is any production that generates it. It doesn't matter if there are other productions (e.g., 'endless loops') that are pointless or never generate any word; they're harmless and irrelevant.

No, this will not yield abababab.. as valid.