Je me bats à la traduction de EBNF à BNF

Question

J'apprends des compilateurs et des concepts de langages de programmation. Comment puis-je le traduire?

Problème:

<S> → (+ | -)[<C>]{<A>} 

Au début, je traduit comme ceci:

<S> -> epsilon 
    | +<S> 
    | -<S> 
    | <C><S> 
    | <A><S> 

Cependant, il a un problème qu'il peut reproduire C!

Answer 1

Votre version BNF peut non seulement produire plusieurs <C> s, mais aussi plusieurs + s et - s (ou zéro, ce qui serait également différent de la grammaire d'origine). Pour résoudre ces problèmes, vous devrez introduire des terminaux supplémentaires. Plus précisément, vous pourriez en avoir un qui correspond à {<A>} et un qui correspond à [<C>]. Votre définition de <S> pourrait alors être:

<S> -> + <OptionalC> <RepeatedA> 
    | - <OptionalC> <RepeatedA> 

Answer 2

Votre original EBNF n'est pas récursive dans <S>, mais votre période d'essai est BNF. Si vous voulez que la BNF génère le même langage, vous ne devriez pas le faire. En outre, votre EBNF ne peut pas générer epsilon, vous ne devez donc pas l'ajouter à votre production <S>.

Comme autre réponse dit, vous devez introduire non-terminaux supplémentaires:

<S> -> <plusminus> <optionalC> <repeatedA> 
<plusminus> -> + | - 
<optionalC> -> <C> | epsilon 
<repeatedA> -> <A> <repeatedA> | epsilon 

Ceci est une traduction directe des éléments EBNF dans votre grammaire originale. Même si vous avez des exigences supplémentaires (comme l'élimination d'epsilon), vous devriez commencer par ce genre d'étape.

Notez que la règle <S> n'est pas récursive. En outre, bien que epsilon soit utilisé pour certains non-terminaux supplémentaires, il ne fait pas partie des règles <S> ou <plusminus>, de sorte que, comme dans l'original EBNF, <S> ne peut pas le produire.