Обсуждение:Форма Бэкуса–Наура


Другие ранние грамматические спецификации

Примерно в то же время, когда BNF использовался в Algol, Тони Брукер и другие использовали очень похожую нотацию, которая в конечном итоге была использована в Compiler Compiler. В статье говорится: «"Система построения компилятора", разработанная Брукером и Моррисом, напрямую использовала BNF». Но на самом деле это не так, она использовала их собственный формат грамматики, и хотя я не могу предоставить доказательств, я понимаю, что это было полунезависимое изобретение идеи, которая витала в сообществе в то время. Я не собираюсь заходить так далеко, чтобы предполагать, что Брукер изобрел BNF, но, безусловно, его современная работа была на одном уровне с ней. Я отмечаю, что в публикации "The Compiler Compiler" имя Бэкуса нигде не упоминается. Тони был не из тех людей, которые присвоили себе чужую заслугу, поэтому я думаю, что это упущение косвенно подтверждает идею о том, что формат грамматики, используемый в Compiler Compiler, был их собственной работой. Дата 1963 года на этой статье не является датой первого использования формата. Боюсь, я не знаю, когда Тони впервые использовал формальную грамматику при построении парсеров, но было бы интересно взглянуть. Обратите внимание, что в то время BNF использовался только описательно в проекте Algol 60, тогда как Тони фактически использовал его при создании парсеров. Я упоминаю все это исключительно как комментарий к Talk, поскольку у меня нет жестких ссылок, чтобы поместить их в основную статью. 70.124.38.160 (обсуждение) 03:04, 17 апреля 2024 (UTC) [ ответить ]

К тому времени Algol 60 уже был хорошо известен. Почему бы просто не предположить, что они взяли подход из отчета Algol 60? Rp ( talk ) 20:29, 17 апреля 2024 (UTC) [ ответить ]
Ну, я почти уверен, что Тони Брукер использовал этот формат до отчета Algol 60. Я полагаю, что он уже использовал что-то похожее к моменту предложения IAL в 1958 году. Atlas Autocode Тони был ответом на предложение IAL, а не ответом на отчет Algol 60, и он определенно уже использовал структурированную грамматику этого общего стиля до своей реализации Atlas Autocode. Тони, в частности, не был приглашен на встречу в Цюрихе в 58 году (я почти уверен, что если бы он был приглашен, Algol 60 имел бы меньше особенностей, против которых Тони возражал и которых избегал в своем языке Atlas Autocode), и я не думаю, что многое из того, что он делал тогда, было под влиянием работы Algol 60 или людей — он был в Манчестере, делая свое дело по-своему. Он определенно думал о грамматиках в стиле BNF в 58-м, когда начал работать над компилятором-компилятором, но использовал ли он уже этот формат к тому времени для какого-либо другого проекта, я не могу быть на 100% уверен. Если я смогу найти ссылку <= 1958 на использование Тони грамматик, я добавлю ее здесь, и хотя я уверен, что они есть, у меня их нет под рукой. Возможно, он использовал грамматику при написании Mercury Autocode, но я не могу вспомнить и не искал в сети источники Mercury Autocode, чтобы проверить. 70.124.38.160 (обсуждение) 22:25, 19 апреля 2024 (UTC) [ ответить ]
Может быть, ссылка? https://www.sciencedirect.com/science/article/abs/pii/B9781483197791500069 - ясно показывает, что он использовал фразовую структурированную грамматику для реализации Mercury Autocode. Статья была опубликована в 1961 году, но я считаю, что сам Mercury Autocode был написан к 1958 году. Саймон Лавингтон упомянул (выделено мной):
Следующий компьютер Manchester, Ferranti Mercury, имел аппаратное обеспечение с плавающей точкой, но проблемы с управлением памятью все еще присутствовали. К 1958 году Тони разработал Mercury Autocode, который расширил лингвистическое богатство Mark I Autocode, не предоставив при этом общего решения проблемы двух уровней хранения Mercury (основного и барабанного). в https://curation.cs.manchester.ac.uk/atlas/docs/Brooker%20Atlas%20CC%20rev%20April%202016bb.pdf 70.124.38.160 (обсуждение) 22:44, 19 апреля 2024 (UTC) [ ответить ]
Общая программа перевода для языков фразовой структуры (Брукер и Моррис): https://dl.acm.org/cms/asset/95e0a22b-1077-42c0-b156-54ca3509f3cd/321105.321106.fp.png ( https://dl.acm.org/doi/10.1145/321105.321106 )
Программа сборки для языка фразовой структуры (Брукер и Моррис): https://academic.oup.com/comjnl/article/3/3/168/345484
Опубликовано в 1960 году, но ссылается на более ранние работы. Эти идеи витали в сообществе в масштабе времени 58-60 годов, и Компилятор Компилятор определенно реализовал синтаксический анализ на основе ввода этого стиля грамматики - первое использование явно раньше 1972 года, который Пол Б. Манн ошибочно утверждал в "Трансляционной нотации грамматики BNF" https://dl.acm.org/doi/10.1145/1147214.1147218 "Нотация грамматики BNF появилась около 1960 года для спецификации языков программирования. Впервые она была использована для автоматической генерации синтаксических анализаторов около 1972 года."
Кстати, отдавая должное Тони, я упомяну, что алгоритм «PEG Parser» — это тот же алгоритм, который Тони использовал в своих парсерах, включая Compiler Compiler (за исключением компонента мемоизации, который является всего лишь тривиальным применением Memo Functions Дональда Мичи из 1967 года https://stacks.stanford.edu/file/druid:kr445kk4694/kr445kk4694.pdf ). 70.124.38.160 (обсуждение) 01:03, 20 апреля 2024 (UTC) [ ответить ]

Похожее программное обеспечение?

@ ComputerUserUser и Smuckola : Smuckola, вы изменили заголовок «Программное обеспечение, принимающее BNF-подобный ввод» на «Аналогичное программное обеспечение», утверждая, что предыдущий был расплывчатым. Прежний заголовок был предельно ясен, но именно новый кажется мне двусмысленным и расплывчатым. Я думаю, его следует вернуть обратно. Джейсон Куинн ( обсуждение ) 08:53, 7 июля 2024 (UTC) [ ответить ]

Специальный символ «удалить»

На момент написания статьи раздел «Обзор» заканчивался следующим предложением:

Применение правил таким образом может производить все более длинные последовательности, поэтому многие определения BNF допускают включение в спецификацию специального символа «удалить». Мы можем указать правило, которое позволяет нам заменять некоторые символы этим символом «удалить», который должен указывать на то, что мы можем удалить символы из нашей последовательности и при этом иметь синтаксически правильную последовательность.

Я не знаком с символом «удалить», о котором там идет речь, и мне не ясно, какую проблему он призван решить. Конечно, это не значит, что его не существует, но в цитате, приведенной для этого предложения (http://www.cs.umsl.edu/~janikow/cs4280/bnf.pdf), эта концепция вообще не упоминается (и это, похоже, был бы странный выбор цитаты, даже если бы он упоминался), поэтому я по-прежнему не могу определить, о чем там идет речь.

Описывает ли предложение что-то значимое? Если да:

  1. Можно ли привести реальную ссылку на него?
  2. Действительно ли это относится к обзору?

Предложение было добавлено здесь: https://en.wikipedia.org/w/index.php?title=Backus%E2%80%93Naur_form&diff=next&oldid=1204483713 Bhathos (обс.) 04:31, 21 сентября 2024 (UTC) [ ответить ]

В цитате упоминается символ (стр. 2, 2-й пункт снизу), но он не называется «символом удаления». Любая грамматика, использующая символ удаления, может быть преобразована в грамматику, не использующую его и описывающую тот же язык (за исключением пустой строки; см. Context-free_grammar#Reachability,_productiveness,_nullability ). Предложение из раздела «Обзор» создает впечатление, что цель символа удаления — получение более коротких последовательностей, что является вопиющей бессмыслицей. - Йохен Бургхардт ( обсуждение ) 05:39, 23 сентября 2024 (UTC) [ ответить ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Backus–Naur_form&oldid=1269220678"