Четох, че повечето езици за програмиране могат да бъдат анализирани като граматика без контекст (CFG). По отношение на изчислителната мощност той се равнява на този на недетерминиран автомат с натискане надолу. Прав ли съм?
Технически да. Полезно, не
Има поне два полезни начина да мислите по тези въпроси:
- Ако мислите за набор от низове, имате език.
- Ако мислите за алгоритъм, който да реши дали даден низ е или не е на език, имате проблем с решението.
Трудността е, че докато повечето езици за програмиране имат основна структура, която лесно се описва от контекстно-свободна граматика (Tcl е интересно изключение), много изречения, които са описани от контекстно-свободната граматика, всъщност не са „в език“, където под „на езика“ имам предвид „валидна програма на въпросния език“. Тези допълнителни изречения обикновено се изключват от някаква форма на статична семантика. Например, следното изказване е изречение в безконтекстната граматика на C програми, но самото то не е в набора от валидни C програми:
int f(void) { return n + 1; }
Проблемът тук е, че n не е в обхват. C изисква "декларация преди употреба" и това свойство не може да бъде изразено с помощта на контекстно-свободна граматика.
Типична процедура за вземане на решение за истински език за програмиране е част от предния край на компилатор или интерпретатор и има поне две части: едната, парсер, е еквивалентна в силата на вземане на решения за натискащ автомат; но вторият прави допълнителни проверки, които изключват много изказвания като невалидни. Ако тези проверки изискват някакъв вид свойство за дефиниране преди употреба, те не могат да бъдат направени от автомат за натискане или контекстно-свободна граматика.
Ако е вярно, тогава как може CFG да съдържа неограничена граматика (UG), която е завършена по Тюринг?
CFG не "съдържа" нищо, той просто описва език.
... дори ако езиците за програмиране са описани от CFG, те всъщност се използват за описание на машини на Тюринг и така чрез UG.
Прескачате някои важни нива на индиректност тук.
Мисля, че това се дължи на най-малко две различни нива на изчисление, първото, което е парсването на CFG, се фокусира върху синтаксиса, свързан със структурата (представяне?) на езика, докато другото се фокусира върху семантиката ( смисъл, интерпретация на самите данни?), свързани с възможностите на езика за програмиране, който е завършен. Отново, верни ли са тези предположения?
Изглеждат ми малко объркани, но си на прав път. Ключов въпрос е "каква е разликата между език и програмен език?" Отговорът е, че езикът за програмиране има изчислителна интерпретация. Изчислителните интерпретации се предлагат в много фини разновидности и не всички от тях са пълни по Тюринг. Но магията е в интерпретацията, а не в синтаксиса, така че йерархията на Чомски не е много уместна тук.
За да докажа моята теза, краен пример: обикновеният език [1-9][0-9]* е пълен по Тюринг при следната интерпретация:
- Езикът на SK-комбинатора е завършен по Тюринг.
- Има само безброй много SK програми.
- Те могат лесно да бъдат изброени еднозначно и детерминистично.
- Следователно можем да свържем всяко положително цяло число с SK програма.
- Ако интерпретираме поредица от цифри като положително цяло число по стандартния начин, можем еднакво добре да интерпретираме същата поредица от цифри като SK програма и освен това всяка SK програма може да бъде изразена с помощта на краен последователност от цифри.
Следователно езикът на целочислените литерали е пълен по Тюринг.
Ако сега не те боли главата, трябва.
person
Norman Ramsey
schedule
01.06.2010
