Récursif de la Descente de l'Analyseur en Java
Je voudrais commencer en disant que c'est un devoir maison pour ma troisième Année de Langages de Programmation de Classe, et je suis à la recherche d'un peu d'aide avec elle. Ma mission se lit comme suit:
Date limite: le 22 février 2013 à 11:55pm
Présentation: s'il vous Plaît télécharger la suite de la CMS.1. Le code Source
2. Une capture d'écran de l'exécution de votre programme, y compris le fichier d'entrée utiliséUtiliser tout langage de programmation vous préférez écrire un appel récursif à la descente de l'analyseur qui analyse le langage généré par le texte suivant EBNF descriptions. Votre analyseur doit détecter si oui ou non le programme d'entrée a des erreurs de syntaxe. Il n'a pas à préciser en quoi et où est l'erreur.
<program> begin <stmt_list> end
<stmt_list> <stmt> {;<stmt_list>}
<stmt> <assign_stmt> | <while_stmt>
<assign_stmt> <var> = <expr>
<var> identifier (An identifier is a string that begins with a letter followed by 0 or more letters and digits)
<expr> <var> { (+|-) <var>}
<while_stmt> while (<logic_expr>) <stmt>
<logic_expr> ® <var> (< | >) <var> (Assume that logic expressions have only less than or greater than operators)
Les symboles de l'air bizarre sont juste des flèches pointant vers la droite.
Mon problème du moment, c'est plus logique alors c'est la programmation: dans ma première tentative, j'ai lu l'intégralité du programme d'entrée dans sauvegardé sur une chaîne, puis analysé cette chaîne et convertis chaque symbole à un terminal, expr, ou ce que vous avez.
Finalement, j'ai trouvé que ce moyen ne serait pas de travail parce que, de Un: je ne pense pas que c'est RDP, B: nombre des non terminaux sont faits de plus de 1 instruction.
J'ai renoncé à cette approche, et décidé avant que je ne perdons plus de temps à la programmation, je voudrais Pseudo tout. Mon idée était de faire de la méthode 1, pour chaque symbole non terminal, et juste analyser la chaîne d'entrée symbole par symbole, en espérant entre ces méthodes. Cette approche semble logique, mais comme j'ai commencé à écrire le pseudo-code j'ai tout perdu et confus quant à ce que je devais faire. Comment aurais-je terminer ce code?
Voici quelques pseudo-code de RDP:
intputString;
public void parseProgram (Symbol.typeIsProgram) {
if getNextSymbol == "begin" {
if (intputString.substring (inputString.length()-3,
inputString.length()) == "end") {
Symbol stmt_lsit = new Symbol (intputString)
parseStmt_list(stmt_list);
} else {
Out "error, prog must end with end"
}
} else {
Out "error, prog must begin with begin"
}
}
public void parseStmt_list (Stmbol.typeIsStmt_list) {
symbol = getNextSymbol;
if (Symbol.typeIsVar) {
parseVar(symbol)
} else if (Symbol.typeIsWhile) {
//weve only capture if the first word return is a while, we dont have the whole while statement yet
ParseWhile_stmt(symbol)
} else { }
}
public void parseStmt () { }
public void parseAssign_stmt () { }
public void parseVar () { }
public void parseExpr () { }
public void parseWhile_stmt () { }
public void parseLogic_expr () { }
public Symbol getNextSymbol() {
//returns the next symbol in input string and removes it from the input string
}
Juste un avis d'un échantillon du programme d'entrée pour mon analyseur serait.
begin
total = var1 + var2;
while (var1 < var2)
while ( var3 > var4)
var2 = var2 - var1
end
OriginalL'auteur user1972748 | 2013-02-16
Vous devez vous connecter pour publier un commentaire.
Conformément à cette mission en particulier qu'il est bien de l'utilisation du traitement de chaîne de façon fonctionnelle.
Essayez de cet algorithme:
begin
et se termine avecend
;
et faire les étapes suivantes pour chaque partie (la déclaration)=
ouwhile
sous-chaîne+
ou-
et pour chaque partie de vérifier l'état variable (alphanumérique contenu)(
et)
et, récursivement, processus de deux chaînes de caractères entre crochets et après il<
ou>
, et de vérifier que les pièces sont variables (alphanumérique)Peut-être, il n'est pas solution très flexible, mais comme je vois qu'il est acceptable pour votre tâche.
EDIT:
J'ai trouvé la tâche intéressante et essayé d'écrire une solution complète.
OriginalL'auteur Dmitry Tikhonov
1) la Segmentation
Première pause de l'entrée en jetons. Dans ce cas, chaque identificateur d'opérateur et littérale. Faire une grande liste de tous les jetons. Une fois que vous avez les jetons, alors vous pouvez commencer l'analyse. Faire les jetons d'une liste liée, de sorte que vous pouvez juste dire Jeton.Suivant pour lire le prochain jeton ou un Jeton.Prochaine.En regard de lecture 2 jetons à l'avance. Mettre un tas d'expressions du FOLKLORE jetons à la fin de sorte que vous ne serez jamais passer.
2) Analyse des
L'analyse est comme ce que vous avez déjà. Ainsi, au lieu de penser Symbole pense Jeton. Le Parse liste est une boucle while qui garde l'analyse des déclarations jusqu'à la fin.
Pour Analyser Déclaration
Analyse de l'instruction while boucle de retour de parse et donc il va "récursivement descendre" dans l'Analyser déclaration, produisant des boucles while imbriquées etc...
L'analyse de l'instruction d'affectation est très similaire. Analyser le côté Gauche puis le côté droit. Vous avez besoin d'un tas de fonctions pour....
Le Nœud voici un nœud de l'Ast. Arbre De Syntaxe Abstraite.
Des trucs comme...
Si vous suivez la logique que vous pouvez voir comment les règles de priorité sont suivis de manière récursive en arrivant à chaque cible. L'analyse des expressions et des partir de le céder n'est pas une boucle. C'est comme montré ici. Évidemment, cela est simple, mais il montre la technique.
De sorte que le RDP est causée par la recherche au cours de jeton et puis en sautant sur une fonction pour gérer jeton. Naturellement, cela ne peut revenir à la même fonction est donc récursive. Si vous regardez la ParseSimpleExp fonction, alors vous pouvez voir que c'est un bon endroit pour peut-être la poignée d'une mise entre parenthèses de l'expression. Un des parens expression sera la cause de la récursivité retour à la simple exp et, éventuellement, les autres comme mul et add.
OriginalL'auteur
La structure de votre analyseur de code doit ressembler à la structure de la langue syntaxe.
E. g.
pourrait se traduire par quelque chose comme
Vous pourriez ne pas confondre le jeton de manutention (scanner) avec l'analyse de la structure (analyseur).
J'irais avec la gestion des exceptions au lieu de if /else structures pour la gestion des erreurs.
Vous voudrez peut-être garder trace de l'endroit où vous êtes dans la source (scanner) de la partie pour l'affichage d'un message d'erreur approprié. Il suffit de demander le scanner pour son état.
La cession heureusement semble avoir besoin d'aucune résolution des conflits afin que votre récursive décent devrait bien fonctionner. La partie intéressante est où dans l'analyse de
vous aurez pour appeler
parse_stmt()
de manière récursive. C'est ce que l'idée de la descente récursive d'analyse est d'environ.OriginalL'auteur Wolfgang Fahl