L'automate à pile est-il utile dans ce cas?

Question

Dans l'université, ils me demandent d'utiliser la grammaire et l'automate Pushdown pour vérifier la syntaxe d'une partie du code Java. Du fait que je n'ai pas encore utilisé cet automate, j'ai appris un peu comment ils fonctionnent et je pense que cet automate n'est pas très utile pour vérifier la syntaxe du code car l'automate à pile est utilisé pour vérifier une grammaire avec une certaine proportion comme "0^n 1^2n | n> = 0".

Ces proportions entre les jetons ne sont pas présentes dans la syntaxe du code, donc je pense que l'automate à pile n'est pas utile dans ce cas.

• J'ai raison?
• dois-je me plaindre de ce travail qu'ils me demandent?

Answer 1

Les grammaires non déterministes (NPDA) et les grammaires sans contexte (CFG) ont la même puissance dans la représentation des langues.

Comme la plupart (sinon la totalité) d'une syntaxe de langage de programmation (comme java) peut être présentée par un CFG, elle peut aussi être présentée par un NPDA.

Alors, ne vous plaignez pas, faites l'assignation.