Контекстно-зависимые и полные по Тьюрингу формальные языки

Знаете ли вы о каких-либо, которые могут задавать контекстно-зависимую грамматику? Например * разрешение неоднозначности указателя символа/умножения. Я ищу формальный язык, который позволит разрешить такие двусмысленности. Язык, который я ищу, должен быть четко указан.

Изменить: я ищу что-то вроде BNF, но оно должно быть контекстно-зависимым, на самом деле оно должно решать Dangling другая проблема.


formal-languages context-sensitive-grammar
person user3313119    schedule 23.04.2014    source источник
comment
С++, безусловно, отвечает всем требованиям (он очень контекстно-зависим)   -  person Basile Starynkevitch    schedule 23.04.2014
comment
По иронии судьбы, ваш вопрос сам по себе неоднозначен, или, по крайней мере, я совершенно не могу его разобрать. Не могли бы вы уточнить/перефразировать, что вам нужно и какими свойствами оно должно обладать?   -  person    schedule 23.04.2014
comment
Я ищу формальный язык, который может разрешать различия в разборе между указателями и символами умножения, не предоставляя некоторые внешние процедуры. Что-то вроде BNF, но должно быть контекстно-зависимым.   -  person user3313119    schedule 23.04.2014
comment
Я не уверен, достаточно ли контекстно-зависимых грамматик, чтобы отличить объявление указателя от умножения (люди всегда говорят, что это контекстно-зависимо, но у меня сложилось впечатление, что большинство из них используют неформальное, возможно, очень неправильное определение контекстной чувствительности) . В любом случае тривиальным решением будет любой полный по Тьюрингу язык; Я предполагаю, что вы намеревались исключить это, не предоставляя некоторые внешние процедуры? Если это так, вам придется сделать это более формальным/конкретным, эта формулировка может означать почти что угодно.   -  person    schedule 23.04.2014

Ответы (1)


arrow_upward
4
arrow_downward

БНФ может разрешать неоднозначности такого рода путем введения дополнительных правил. Например, в спецификации языка Java вы найдете:

IfThenStatement:
  if ( Expression ) Statement
IfThenElseStatement:
  if ( Expression ) StatementNoShortIf else Statement
StatementNoShortIf:
  IfThenElseStatementNoShortIf
  ...
IfThenElseStatementNoShortIf:
  if ( Expression ) StatementNoShortIf else StatementNoShortIf

...где StatementNoShortIf - это Statement, которое не может заканчиваться на "если", у которого нет "иначе". Таким образом, если я разбираю if(a) if(b) c(); else d();, то единственный вариант — привязать if(b) c(); else d(); к StatementNoShortIf.

person Russell Zahniser    schedule 23.04.2014