Grammaire BNF pour la séquence d'instructions

Question

Si je fais une grammaire pour un langage de type c qui a une suite d'énoncés, quelle est la manière la plus courante de définir la grammaire?

Ma pensée est de faire quelque chose comme ceci:

<program> ::= <statement> 
<statement> ::= <statement-head><statement-tail> 
<statement-head> ::= <if-statement> | <var-declaration> | <assignment> | <whatever> 
<statement-tail> ::= ; | ;<statement> 

mais qui se sent un peu maladroit pour moi. J'ai aussi envisagé de faire

<program> ::= <statement>* 

ou

<statement> ::= <statement-head> ; | <sequence> 
<sequence> ::= <statement> <statement> 

productions de type.

Existe-t-il une manière standard ou acceptée de le faire. Je veux que mon AST soit aussi propre que possible.

Answer 1

Une façon très courante serait:

<block-statement> ::= '{' <statement-list> '}' ;
<statement-list> ::= /* empty */ | <statement-list> <statement> ;
<statement> ::= <whatever> ';' ;


Et puis vous définissez les déclarations réelles au lieu de taper <whatever>. Il semble beaucoup plus propre d'inclure des points-virgules dans les déclarations individuelles plutôt que de les mettre dans la définition de la liste non-terminale.

Answer 2

Vous pouvez trouver le BNF pour C here et je pense qu'il a été pris de K & R, que vous pourriez vérifier. Vous pouvez également consulter le SQL BNF here qui peut fournir plus d'informations sur la formulation de bonnes séquences.

Ceci fournira des informations sur la convention.

En termes de génération d'AST, peu importe à quel point votre définition est «maladroite» si elle fournit une analyse correcte de la source pour toutes les permutations. Ensuite, ajoutez simplement les actions pour construire votre AST. Assurez-vous simplement que vous construisez votre grammeur pour le bon générateur d'analyseur, tel qu'un analyseur LL ou LR, car vous risquez de rencontrer des problèmes de réduction, ce qui signifie que certaines règles doivent être réécrites d'une nouvelle manière. Voir ceci sur eliminating left recursion. Vous pouvez également consulter des exemples Bison/Yacc tels que these ou these. Consultez également le Dragon Book et un livre intitulé « Mise en œuvre moderne compilateur C »