Синтаксические анализаторы и компиляторы для макетов.С чего начать? [дубликат]

Взгляните на: обучение записать компилятор

Также интересный:

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

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

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

Следующий шаг должен перевести tokenstream в syntaxtree или другое представление. Это называют шагом парсинга.

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

Маркеры

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.

Лексический анализатор

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

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

Синтаксический анализатор

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

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

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

Я надеюсь, что это разъяснилось немного ;-).