Основной вопрос: как я могу обновить свой синтаксический анализатор рекурсивного спуска для логики высказываний (написанный на JavaScript), чтобы строки типа "p ~" и "pp" возвращали сообщение "Invalid"?
Я очень плохо знаком с HTML, JavaScript и синтаксическим анализом. Я хотел посмотреть, смогу ли я создать простую веб-страницу, которая сможет отделить простые формулы от логики высказываний. Вот грамматика:
<formula> ::= <unaryconnective> <formula>
| "(" <formula> <binaryconnective> <formula> ")"
| <proposition>
<unaryconnective> ::= "~"
<binaryconnective> ::= "&"
<proposition> ::= "p"
| "q"
| "r"
Я новичок в написании таких грамматик, так что, надеюсь, эта грамматика имеет смысл. Насколько я понимаю, что в Википедии было на левой рекурсивной грамматике, я не верю, что эта грамматика остается рекурсивной, и при этом она не выглядит неоднозначной.
Затем я попытался создать простую веб-страницу, которая позволяла бы кому-то вводить формулу в текстовое поле, нажимать кнопку «Подтвердить» и возвращать простое сообщение о том, что формула верна или нет. Я попытался написать парсер рекурсивного спуска, который мог бы выполнить анализ. Вот что я придумал, основываясь на том, что Википедия, Переполнение стека и другие ресурсы, которые я нашел по этой теме ( jsfiddle ):
<!DOCTYPE html>
<html lang='en'>
<head>
<meta charset='UTF-8'>
<title>Logic App</title>
<script type="text/javascript">
var sentence;
var len;
var i;
var sym;
function validate() {
var result;
sentence = document.getElementById('formulaentry').value;
len = sentence.length;
i = -1;
if (sentence == "") {
document.getElementById('formulaentry').value = "There's no formula!";
} else {
nextSym();
result = formula();
if(result == 0) {
document.getElementById('formulaentry').value = "Invalid";
} else {
document.getElementById('formulaentry').value = "Valid";
}
}
}
function nextSym() {
i++;
if (i <= (len-1)) {
sym = sentence.charAt(i);
} else {
sym = "";
}
//console.log("Current Sym:" + sym);
}
function accept(s) {
if (sym == s) {
nextSym();
return 1;
}
return 0;
}
function expect(s) {
if (accept(s)) {
return 1;
}
return 0;
}
function formula() {
if (unaryconn(sym)) {
nextSym();
if (formula() == 0) return 0;
return 1;
} else if (accept("(")) {
if (formula() == 0) return 0;
if (binaryconn(sym) == 0) return 0;
nextSym();
if (formula() == 0) return 0;
if (!expect(")")) return 0;
return 1;
} else if (proposition(sym)) {
nextSym();
return 1;
} else {
return 0;
}
}
function unaryconn(s) {
if (s == "~") {
return 1;
} else {
return 0;
}
}
function binaryconn(s) {
if (s == "&") {
return 1;
} else {
return 0;
}
}
function proposition(s) {
if (s == "p" || s == "q" || s == "r") {
return 1;
} else {
return 0;
}
}
</script>
</head>
<body>
<h1>Logic App</h1>
<h2>Check if formula is well-formed:</h2>
<p>Enter a formula into the text box and click "Validate" to see if it is a
wff.</p>
<form id='frmValidateFormula'>
<p>
<input
type='text'
id='formulaentry'
placeholder='Input formula here'>
</p>
<p>
<input
type='button'
id='btnValidate'
value='Validate'
onclick='validate()'>
</p>
</form>
</body>
</html>
Парсер, кажется, в основном работает. Он правильно анализирует следующие строки как правильную формулу:
p
~p
(p&p)
~(p&p)
(~(p&~~p)&(~p&~p))
Однако он неправильно возвращает «Действительный» для этих строк, когда должен возвращать «Недействительный»:
p~
pp
~p~
p&
p(
p)
ppqqpqpq
Похоже, что анализатор не проверяет всю строку в этих случаях, только символы, ведущие к первой букве, и саму букву, и поэтому считает, что это нормально. Я попытался добавить какой-то вид проверки в формулу () в разделе «else if (уждение (sym)»), чтобы убедиться, что символ, следующий за буквой, является допустимым, но это не сработало, поскольку действительные символы меняются в зависимости от того, что до этого. Изменение моей грамматики может помочь. Я не совсем понимаю, что я должен учитывать при создании этих грамматик, отличных от того, что левая рекурсия вызовет проблемы для анализатора рекурсивного спуска. Я рассмотрел несколько вопросов о переполнении стека, касающихся рекурсивного спуска парсеры, но никто не помог мне с моей проблемой.
Как я могу обновить свой парсер, чтобы такие строки возвращали "Invalid" в результате? Я не обязательно ищу полный ответ, просто некоторые указатели на вещи, чтобы рассмотреть или ресурсы, чтобы посмотреть. Если вы также знаете хороший ресурс о том, о чем думать при построении грамматик (особенно со ссылкой на парсеры), это было бы замечательно.
Примечание. В настоящее время мой анализатор не обрабатывает пробелы. Сейчас я в порядке с этим, поскольку в основном меня интересует, как правильно разобрать другой синтаксический анализ перед обновлением вещей для обработки пробелов.