Контекстно-свободная грамматика - это описание набора строк, которое строго более мощное, чем регулярные выражения, но все же легко обрабатываемое машиной.Более формально, контекстно-свободная грамматика состоит из четырех вещей:
Набор терминальных символов , которые являются элементами производимых строк.Для синтаксического анализатора бизонов это обычно набор токенов, генерируемых сканером.Для грамматики для естественного языка, такого как английский, это может быть набор всех английских слов.
Набор нетерминальных символов .Интуитивно понятно, что нетерминальный символ представляет нечто вроде части речи, такой как «существительное» или «глагол».
Набор произведений. Каждое произведение говорит, какзаменить нетерминальный символ другим набором терминалов и нетерминалов.Например, производство Variable -> Type Name говорит, что если мы увидим нетерминал Variable, мы можем заменить его строкой Type Name.
A начальный символ, , который является нетерминалом, с которого начинается деривация.
В качестве примера рассмотрим эту простую контекстную грамматику для объявлений функций в стиле C:
Function -> Type ident(Arguments)
Type -> int
Type -> Type *
Arguments -> e (the empty string)
Arguments -> ArgList
ArgList -> Type ident
ArgList -> Type ident, ArgList
Здесь начальный символ Function.Учитывая эту грамматику, мы можем создавать объявления функций в стиле C, многократно выбирая нетерминальный символ и заменяя его одной из правых частей соответствующего произведения.На каждом шаге строка, которую мы до сих пор строили, называется формой предложения .Например, вот несколько различных объявлений функций, которые могут быть получены из приведенной выше грамматики:
Sentential Form Production
-------------------------------------------------------------------
Function Function -> Type ident(Arguments)
Type ident(Arguments) Type -> int
int ident(Arguments) Arguments -> e
int ident()
Sentential Form Production
-------------------------------------------------------------------
Function Function -> Type ident(Arguments)
Type ident(Arguments) Type -> Type*
Type* ident(Arguments) Type -> int
int* ident(Arguments) Arguments -> ArgList
int* ident(ArgList) ArgList -> Type ident, ArgList
int* ident(Type ident, ArgList) ArgList -> Type ident
int* ident(Type ident, Type ident) Type -> Type*
int* ident(Type* ident, Type ident) Type -> Type*
int* ident(Type** ident, Type ident) Type -> int
int* ident(int** ident, Type ident) Type -> int
int* ident(int** ident, int ident)
Большинство языков программирования имеют структуру, которая может быть описана безконтекстной грамматикой.Работа синтаксического анализатора состоит в том, чтобы взять программу и грамматику и определить, как эта программа может быть сгенерирована грамматикой.
Что касается LALR (1), к сожалению, формальное определение LALR (1) не являетсятривиальный.Я только что закончил преподавать курс по компиляции, и мы смогли поговорить о LALR (1) только после того, как сначала провели две лекции, обсуждая связанные методы разбора.Если вы хотите получить официальное введение в материал, мои слайды по анализу снизу вверх доступны на сайте курса .
LALR (1) являетсятип алгоритма синтаксического анализа, называемый восходящим алгоритмом синтаксического анализа , что означает, что он пытается применить производство грамматики в обратном порядке, чтобы уменьшить программу обратно к начальному символу.Например, давайте рассмотрим эту строку, которая генерируется приведенной выше грамматикой:
int** ident(int* ident)
При анализе снизу вверх мы будем анализировать эту строку, просматривая программу по одному токену за раз.Всякий раз, когда мы обнаруживаем что-то, что может быть обращено обратно к какому-то нетерминалу, мы делаем это.(Чтобы быть более точным, LALR (1) делает подобные сокращения только тогда, когда встречаются другие критерии, так что алгоритм имеет больше контекста, но для этого примера нам не нужно беспокоиться об этом).Каждый шаг в разборе называется либо сдвиг , либо уменьшение . shift означает, что мы смотрим на еще один токен ввода, чтобы получить больше информации о том, какие сокращения применить.* уменьшение означает, что мы берем некоторое количество токенов и нетерминалов и обращаем производство, чтобы вернуться к какому-нибудь нетерминалу.
Вот след восходящего анализа строки:
Workspace Input Action
-----------------------------------------------------------------
int** ident(int* ident) Shift
int ** ident(int* ident) Reduce Type -> int
Type ** ident(int* ident) Shift
Type* * ident(int* ident) Reduce Type -> Type*
Type * ident(int* ident) Shift
Type* ident(int* ident) Reduce Type -> Type*
Type ident(int* ident) Shift
Type ident (int* ident) Shift
Type ident( int* ident) Shift
Type ident(int * ident) Reduce Type -> int
Type ident(Type * ident) Shift
Type ident(Type* ident) Reduce Type -> Type*
Type ident(Type ident) Shift
Type ident(Type ident ) Reduce ArgList -> Type ident
Type ident(ArgList ) Reduce Arguments -> ArgList
Type ident(Arguments ) Shift
Type ident(Arguments) Reduce Function -> Type ident(Arguments)
Function ACCEPT
Важно знать о сдвигах и сокращениях, потому что вы будете постоянно встречать сдвигать / уменьшать конфликты и уменьшать / уменьшать конфликты при использовании зубров.Эти ошибки означают, что генератор синтаксического анализатора определил, что анализатор может войти в состояние, в котором он не может определить, сдвигать или уменьшать, или какое из двух сокращений он должен выполнить.Обратитесь к руководству по зубрам для более подробной информации о том, как справиться с этим.
Если вы хотите узнать больше о неконтекстных грамматиках и алгоритмах синтаксического анализа в целом, есть отличная книга под названием Методы синтаксического анализа: практическое руководство, второе издание от Грюна и Джейкобса, который, безусловно, является лучшей обработкой материала, который я когда-либо видел. Он охватывает все виды алгоритмов синтаксического анализа, включая многие методы, значительно более мощные, чем LALR (1), которые начинают шире использоваться (например, GLR и Earley). Я очень рекомендую эту книгу - это главная причина, по которой я так хорошо разбираюсь в разборе!
Надеюсь, это поможет!