LR(k)-грамматики - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:40:10Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:34, 1 сентября 2022

2022-09-01T03:34:56Z

Shersh: /* Источники информации */

2016-08-15T10:12:35Z

‎Источники информации

Shersh: /* LR-разборщик */ рефакторинг разбирающей таблицы

2015-09-08T20:28:51Z

‎LR-разборщик: рефакторинг разбирающей таблицы

Shersh: /* Управляющая программа анализатора */ рефакторинг структур

2015-09-08T20:24:17Z

‎Управляющая программа анализатора: рефакторинг структур

Shersh: /* Управляющая программа анализатора */

2015-09-03T18:35:44Z

‎Управляющая программа анализатора

Shersh: /* Управляющая программа анализатора */

2015-09-03T18:35:31Z

‎Управляющая программа анализатора

Shersh: /* Управляющая программа анализатора */

2015-09-03T18:34:28Z

‎Управляющая программа анализатора

Shersh: /* Алгоритм */

2015-09-03T18:34:03Z

‎Алгоритм

Shersh: /* Структура */

2015-09-03T18:33:31Z

‎Структура

← Предыдущая		Версия 16:40, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора\|дерева разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.		'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора\|дерева разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.

← Предыдущая		Версия 03:34, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора\|дерева разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.		'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора\|дерева разбора]]. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.

@@ Строка 111: / Строка 111: @@
 * [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET {{---}} Восходящие анализаторы]
 * [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198-223]
 [[Категория: Методы трансляции]]
 [[Категория: Восходящий разбор]]

@@ Строка 80: / Строка 80: @@
 # Возвращается к первому пункту, пока входная цепочка не закончится.
    '''Result''' algorithmLR(w: '''string''')
        <font color=green>// curToken {{---}} указатель на первый символ в строке w</font>
        '''while''' hasTokens()
            curState = top()
-           '''if''' <tex>\mathtt{T}</tex>[curState, curToken] == Shift s
+           '''when'''(<tex>\mathtt{T}</tex>[curState, curToken])
-              push(curToken)
+              Shift(s) '''->'''
-              push(s)
+                  push(curToken)
-              nextToken()
+                  push(s)
-          '''else if''' <tex>\mathtt{T}</tex>[curState, curToken] == Reduce <tex> A  \to \beta</tex>
+                  nextToken()
-              '''for''' j = 1 '''to''' <tex>|\beta |</tex>
+              Reduce(<tex> A  \to \beta</tex>) '''->'''
-                  pop()
+                  '''for''' j = 1 '''to''' <tex>|\beta |</tex>
-                  pop()
+                      pop()
-              s = top()
+                      pop()
-              push(<tex>A</tex>)
+                  s = top()
-              push(goto(s, <tex>A</tex>))
+                  push(<tex>A</tex>)
-              Вывод правила: <tex> A \to \beta</tex>
+                  push(goto(s, <tex>A</tex>))
-          '''else''' '''if''' <tex>\mathtt{T}</tex>[curState, curToken] == Accept
+                  Вывод правила: <tex> A \to \beta</tex>
-               '''return''' Accept
+              Accept '''->''' '''return''' Accept
-          '''else'''
+               Error  '''->''' '''return''' Error
 Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,

@@ Строка 65: / Строка 65: @@
 *<tex>\mathtt{token}</tex> {{---}} входной символ.
 Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
-  '''enum''' Cell
+  '''struct''' Shift  { state: '''int''' } <font color="green">// переход в состояние с номером state</font>
-     Shift
+  '''struct''' Reduce { rule:  '''int''' } <font color="green">// свертка по правилу с номером rule</font>
-     Reduce
+  '''enum''' Result = Accept   <font color="green">// допуск </font>
-     Error    <font color="green">// ошибка</font>
+             | Error    <font color="green">// ошибка</font>
-     Accept   <font color="green">// допуск </font>
-  '''struct''' Shift
+ '''enum''' Cell = Shift
-     state: '''int'''  <font color="green">// переход в стостояние state</font>
+           | Reduce
-  '''struct''' Reduce
+           | Result
 === Алгоритм ===

@@ Строка 64: / Строка 64: @@
 *<tex>\mathtt{state}</tex> {{---}} состояние автомата,
 *<tex>\mathtt{token}</tex> {{---}} входной символ.
-Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. В случае некорректного входного символа происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
+Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректнен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск:
   '''enum''' Cell
       Shift

@@ Строка 52: / Строка 52: @@
 * входная строка,
 * стек (для запоминания рассмотренных символов),
-* управляющая таблица (для выбора дальнейшего действия {{---}} '''перенос''' или '''свертка'''),
+* управляющая таблица (для выбора следующего действия {{---}} '''перенос''' или '''свертка'''),
 * автомат (для запоминания информации о текущем состоянии стека).