Size: a a a

Compiler Development

2021 June 02

B

Brenoritvrezorkre in Compiler Development
А tree-adjoining grammar (TAG) имеет ту же сложность, что linear indexed grammar (LIG)
источник

B

Brenoritvrezorkre in Compiler Development
Также есть логарифмически редуцируемые контекстно-свободным языки, и они имеют сложность AC¹, которая ⊆ P
источник

YS

Yaroslav Schekin in Compiler Development
Как будто всё, что "выше" CFG, на практике очень полезно, например (по крайней мере, различение этих видов).
Опять-таки, о какой именно практике речь?
источник

AG

Alex Gryzlov in Compiler Development
ну так статья там как раз про различения сортов CFG
источник

B

Brenoritvrezorkre in Compiler Development
Есть ещё и стековые автоматы, детерминированный DSPACE(nlog(n)), недетерминированный NSPACE(n²), и последний сильнее контекстно-чувствительных языков / грамматик
источник

B

Brenoritvrezorkre in Compiler Development
Плюс автоматы, ограниченные разными арифметиками, и на табличке этого тоже нет
источник

YS

Yaroslav Schekin in Compiler Development
Опять-таки, см. https://t.me/CompilerDev/86082
Смысл в различении этих сортов на практике какой?
источник

B

Brenoritvrezorkre in Compiler Development
Ещё можно представить язык истинных квантифицированных булевых формул (TQBF), он находится в PSPACE, на табличке тоже нет
источник

B

Brenoritvrezorkre in Compiler Development
Вы сами сказали, что есть разные практики. Определите, какую практику вы имеете в виду. CFG, например, не описывает естественный язык, и это критично для лингвистов, поэтому они стали разрабатывать грамматики, которые сильнее CFG, но не доходят до CSG
источник

B

Brenoritvrezorkre in Compiler Development
источник

YS

Yaroslav Schekin in Compiler Development
Так вот об этом-то и речь. Для parsing каких-то языков программирования я не вижу каких-то преимуществ, а что там "для лингвистов" — я не в курсе.
Но таких, "которые сильнее CFG, но не доходят до CSG" не бывает, по идее?
Т.е. это какое-то подмножество CSG — следовательно, классифицировать CFG для лингвистов тоже бесполезно, нет? ;)
источник

B

Brenoritvrezorkre in Compiler Development
Я не знаю, что имел в виду Алексей, я не телепат
источник

s

suhr in Compiler Development
CSG это по большей степени просто свалка всего, что не CFG, но ещё разрешимо.
источник

B

Brenoritvrezorkre in Compiler Development
В каком смысле разрешимо?
источник

s

suhr in Compiler Development
Парсинг decidable.
источник

B

Brenoritvrezorkre in Compiler Development
про парсинг ничего не знаю, но если речь бы шла о машинах, которые ограничиваются арифметиками, то арифметика Пресбургера разрешима, но находится где-то между 2-EXP и 2-EXPSPACE, когда как сложность контекстно-зависимых/чувствительных языков (и грамматик) — это NLINSPACE, который равен NSPACE(O(n)).

NSPACE(O(n)), если я не туплю, будет ниже в иерархии, чем NSPACE(n²). В свою очередь NSPACE(n²) ⊂ PSPACE, так как PSPACE = ∪NSPACE(n^k). В свою очередь, PSPACE ⊆ EXP, а 2-EXP выше, чем EXP.
источник

M

MrSmith in Compiler Development
Насколько сильно?
источник

M

MrSmith in Compiler Development
источник

M

MrSmith in Compiler Development
По моему пойдет
источник

а

а это кто in Compiler Development
Круто
источник