Парсеры и компиляторы для чайников. Когда начать?

Ответ 1

Пожалуйста, взгляните на: обучение написанию компилятора

Также интересно:

• как написать язык программирования
• синтаксический анализ, где я могу узнать об этом
• обучающие ресурсы для интерпретаторов и компиляторов парсеров (хорошо, что вы уже упоминали об этом.

И есть еще по теме. Но я могу дать краткое введение:

Первым шагом является лексический анализ. Поток символов преобразуется в поток токенов. Токены могут быть простыми, как == <= + - (и т.д.), И они могут быть сложными, как идентификаторы и числа. Если вам нравится, я могу подробно остановиться на этом.

Следующий шаг - перевести токен в синтаксис или другое представление. Это называется шагом синтаксического анализа.

Прежде чем вы сможете создать парсер, вам нужно написать грамматику. Например, мы создаем парсер выражений:

Жетоны

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.

Язык

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.

Лексер

Мы создаем движок состояния, который проходит через поток char, создавая токен

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

Parser

Настало время создать простой парсер/оценщик. Это полный код. Обычно они создаются с использованием таблиц. Но мы сохраняем это просто. Прочитайте токены и вычислите результат.

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

Это был простой пример. В реальных примерах вы увидите, что обработка ошибок - большая часть анализатора.

Надеюсь, это немного прояснилось: -).

Ответ 2

Если вы полный n00b, наиболее доступный ресурс (в обоих смыслах этого термина), вероятно, учебник Jack Crenshaw. Это далеко не всеобъемлющее, но для начала я не могу придумать ничего близкого, кроме книг, которые давно не печатаются.

Ответ 3

Я хотел бы предложить статью, которую я написал, называемую Реализация языков программирования с использованием С# 4.0. Я пытался сделать его доступным для новичков. Он не является всеобъемлющим, но впоследствии ему должно быть легче понять другие более сложные тексты.