ПО, ЭВМ и АСУ из Таможенного Союза

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » базовые определения » Cтек с графовой структурой (СГС)

Cтек с графовой структурой (СГС)

Страница: 1

Сообщений 1 страница 7 из 7

1

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

Graph Structured Stack (GSS)

Есть статья на английском языке
https://en.wikipedia.org/wiki/Graph-structured_stack
правда там примеры кода не очень удачные, содержат неопределённые функции.
Лучше было бы написать псевдокод.

На русском языке такой статьи (пока?) нет.

Каким могло бы быть её название?

Стек для нескольких вариантов углубления.
Древовидный стек (неточный смысл).
Стек с графовой структурой (нашел этот вариант в интернете)
Стек, представленный в виде графа (из https://oops.math.spbu.ru/SE/YearlyProj … report.pdf)

Изначальная публикация 1988, сейчас 2023 (прошло 35 лет), и во всём виноват Лис?

Tomita Masaru. Graph-structured Stack and Natural Language Parsing
// Proceedings of the 26th Annual Meeting on Association for Computational Linguistics. –– ACL ’88. –– Stroudsburg, PA, USA :
Association for Computational Linguistics, 1988. –– P. 249–257. –– URL:
https://doi.org/10.3115/982023.982054
https://dl.acm.org/doi/pdf/10.3115/982023.982054

Tomita M. Graph-structured stack and natural language parsing. 26th Ann. Meeting of the Association of Computational Linguistics, 7–10 June 1988, Buffalo, New York, USA, pp. 249–257.

Список литературы в работе Томиты:

1987, R. Pareschi & M. Steedman, A Lazy Way to Chart-Parse with Categodal Grammars. 25th Annual Meeting of the Association for Computational Linguistics :81-88.

1987, M. Tomita, An Efficient Augmented-Context-Free Parsing Algorithm. Computational Linguistics 13(1-2):31-46, January-June.

1985, S. Abney & J. Cole., A Govemment-Blnding Parser. In Proceedings of the North Eastern Linguistic Society. XVI.

1985, M. Tomita, Efficient Parsing for Natural Language. Kluwer Academic Publishers, Boston, MA.

1984, G. E. Jr. Barton, Toward a Principle-Based Parser. A.I. Memo 788, MITAI Lab.

1984, E. Wehdi, A Government-Binding Parser for French. Working Paper 48, Institut pour les Etudes Semantiquas et Cognitives, Unlversite de Geneve.

1982, A. E. Ades & M. J. Steedman, On the Order of Words. Linguistics and Philosophy 4(4):517-558,

1977, A. V. Aho & J. D. UIIman, Principles of Compiler Design. Addison Wesley.

1973, M. Kay, The MIND System. Natural Language Processing. ' Algodthmics Press, New York, pages 55-188.

1970, Woods, W. A., Transition Network Grammars for Natural Language Analysis. CACM 13:pp.591-606.

Отредактировано Лис (2023-03-08 08:56:36)

0

2

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

Вместо одного линейного стека используется стек с графовой структурой (GSS — англ. graph-structured stack), который позволяет эффективно хранить различные ветви разбора

МГТУ им. Н.Э. Баумана
Погорелов Д.А. & Таразанов А.М. & Волкова Л.Л.
От LR к GLR: обзор синтаксических анализаторов
uine@bk.ru, a-tarazanov@mail.ru, liliya@bmstu.ru

https://cyberleninka.ru/article/n/ot-lr … alizatorov
страница 4

0

3

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

Пример автоматического перевода:
https://wiki5.ru/wiki/Graph-structured_stack
«Стек с графической структурой»

0

4

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

у них есть слова
2022, Ю. Д. Рязанов & С. В. Назина

Синтаксический анализатор использует стек с графовой структурой (Graph-Structured Stack, GSS) [11] для сохранения позиции возврата после обработки компоненты. Стек с графовой структурой представляет собой направленный граф, где каждый путь является стеком.
...
Если в процессе анализа происходит переход через нетерминальную вершину, то необходимо сохранить информацию об узле, следующем за нетерминальной вершиной, и текущем входе компоненты.
Дуги стека отмечаются узлами леса разбора.

0

5

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

Для начала, надо прочитать исходную работу Томиты. Там разбираются три действия, которые надо уметь делать:
- "Splitting" (Разветвление ветвей стека);
- "Combinig" (Объединение ветвей стека);
- "Local Ambiguity Packing" (Локальное(местное) устранение дублирования)

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

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

Затем надо поискать работу, где это применяется к GLL (потому что в исходной работе это применяется только к GLR).

0

6

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

An efficient algorithm for exploring all traversals of a non-deterministic push down automato (PDA) which performs at most one stack pop and one stack push at each step, was given by Lang [11]. Tomita [12] gave an algorithm aimed explicitly at LR DFAs (which in their standard form can pop multiple stack symbols at each step). The core of Tomita’s algorithm is the data structure known as a Graph Structured Stack (GSS) which represents the multiple stacks which can be generated. The importance of Tomita’s algorithm is the efficient construction of the GSS.

https://core.ac.uk/download/pdf/82073734.pdf

Всё запутали. Теперь надо прочитать про алгоритм из работы 11, найти что за "Tomita’s algorithm" и почему его конструирование стека эффективное.

1974, B. Lang, Deterministic techniques for efficient non-deterministic parsers, in: Automata, Languages and Programming: 2nd Colloquium, in: Lecture Notes in Computer Science, vol. 14, Springer-Verlag, , pp. 255–269.

DOI: 10.1007/978-3-662-21545-6_18
«Please, write to me at Bernard.Lang@datcha.net for my papers. Regards Bernard»

Отредактировано Лис (2023-03-08 09:08:51)

0

7

  • Автор: Лис [Л]
  • Участник
  • Лис [Л]
  • Зарегистрирован: 2021-02-04
  • Приглашений: 0
  • Сообщений: 1027
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 дней 7 часов
  • Последний визит:
    2023-03-10 00:04:11

Есть хештег на GitHub:
https://github.com/topics/graph-structured-stack

https://github.com/ocramz/gss
Haskell 100.0%

https://github.com/developersbk/Universal_Code_Snippets/blob/0001535476a5743c0557c5ce2c3ffc13c6ee8791/Codes/Java/Data_Structures/Java Program to Implement Graph Structured Stack.java

Reference-Counted GSS. This is mostly a minor
    detail, but using reference counting in the GSS produces much
    better locality than garbage collection alone (and manual
    deallocation is impossible due to the nature of the algorithm).
https://github.com/rillian/xgill/blob/b … rithm.html

https://github.com/Virtlink/sdf2table/b … /gss/gss.c
на Си.

Каким требованиям удовлетворяла бы идеальная библиотека?
- она бы могла в интеграцию с потребителями
- и с GraphViz для рисования примеров. (.dot-файлы, кстати, нужен русифицированный аналог)
- возможно что-нибудь с GObject Introspection, чтобы стало доступно в питоне

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

Отредактировано Лис (2023-03-08 10:14:07)

0

Страница: 1

Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » базовые определения » Cтек с графовой структурой (СГС)