Analyseurs et compilateurs pour les nuls. Par où commencer? [dupliquer]

, Veuillez jeter un oeil à: l'apprentissage de l'écriture d'un compilateur

Aussi intéressant:

• comment écrire un langage de programmation
• l'analyse où puis-je apprendre à ce sujet
• ressources d'apprentissage sur les interpréteurs d'analyseurs et les compilateurs (ok vous avez déjà mentionné celui-ci.

Et il y a plus sur le sujet. Mais je peux donner une courte introduction:

, La première étape est l'analyse lexicale. Un flux de caractères est traduit en un flux de jetons. Les jetons peuvent être simples comme ==

L'étape suivante consiste à traduire le tokenstream en un syntaxtree ou une autre représentation. Cela s'appelle l'analyse de l'étape.

Avant de pouvoir créer un analyseur, vous devez écrire la grammaire. Par exemple, nous créons un analyseur d'expression:

Jetons

addOp = '+' | '-';
mulOp = '*' | '/';
parLeft = '(';
parRight = ')';
number = digit, {digit};
digit = '0'..'9';

Each token can have different representations: + and = are both addOp and 
23 6643 and 223322 are all numbers.

Le langue

exp = term | exp, addOp, term;  
// an expression is a series of terms separated by addOps.
term = factor | term, mulOp, factor;
// a term is a series of factors separated by mulOps
factor = addOp, factor | parLeft, exp, parRight | number;
// a factor can be an addOp followed by another factor, 
// an expression enclosed in parentheses or a number.

L'analyseur lexical

Nous créons un moteur d'état qui parcourt le flux char, créant un jeton

s00 
  '+', '-' -> s01       // if a + or - is found, read it and go to state s01.
  '*', '/' -> s02
  '('      -> s03
  ')'      -> s04
  '0'..'9' -> s05
  whitespace -> ignore and retry  // if a whitespace is found ignore it
  else ERROR      // sorry but we don't recognize this character in this state.
s01
  found TOKEN addOp     // ok we have found an addOp, stop reading and return token
s02 
  found TOKEN mulOp
s03
  found TOKEN parLeft
s04
  found TOKEN parRight
s05
  '0'..'9'     -> s05    // as long as we find digits, keep collecting them
  else found number      // last digit read, we have a number

Analyseur

Il est maintenant temps de créer un analyseur/évaluateur simple. Ceci est complet en code. Normalement, ils sont créés à l'aide de tables. Mais nous gardons les choses simples. Lisez les jetons et calculez le résultat.

ParseExp
  temp = ParseTerm // start by reading a term
  while token = addOp do
    // as long as we read an addop keep reading terms
    if token('+') then temp = temp + ParseTerm  // + so we add the term
    if token('-') then temp = temp - ParseTerm  // - so we subtract the term
  od
  return temp // we are done with the expression

ParseTerm
  temp = ParseFactor
  while token = mulOp do
    if token('*') then temp = temp * ParseFactor
    if token('/') then temp = temp / ParseFactor
  od
  return temp

ParseFactor
  if token = addOp then
    if token('-') then return - ParseFactor  // yes we can have a lot of these
    if token('+') then return ParseFactor
  else if token = parLeft then
    return ParseExpression
    if not token = parRight then ERROR
  else if token = number then
    return EvaluateNumber   // use magic to translate a string into a number

C'était un exemple simple. Dans des exemples réels, vous verrez que la gestion des erreurs est une grande partie de l'analyseur.

J'espère que cela clarifie un peu ;-).