Мобильная версияЗадание:
Типы языковых токенов:
- Целые числа — это непустые последовательности цифр, которым может предшествовать символ ' Знак +' или '-'.
- Десятичные числа — это целые числа, за которыми следует символ ".", за которым следует знак ".". непустая последовательность цифр.
- Строки — это любые непробельные последовательности символов, заключенные в "" . например «привет» «abc123».
- Ключевые слова — это следующие строки: 'PRINT', '.', '[', ']', '(', ')' и '^'.
Примечание: ключевые слова написаны заглавными буквами. - Операторы — это специальные строки. В этом домашнем задании мы будем использовать ':-', '~', '', '=', '#', '+', '-', '&', 'OR', '*' , '/' и 'AND'.
- Идентификаторы — это последовательности цифр или букв. Первый символ должен быть буквой, а идентификатор не может быть ключевым словом.
ПРИМЕЧАНИЕ. Для этого присваивания вашему синтаксическому анализатору не требуется обрабатывать комментарии к строкам.
Примеры
Пример 1
Ввод:
Код: Выделить всё
x :- 2 + 2 .
PRINT ( x * 100 ) .
Код: Выделить всё
VALID
Ввод:
Код: Выделить всё
x :- 1 .
a [ i ] :- 2 .
w [ 3 ] ^ ch :- "a" .
t ^ key :- s .
p ^ next ^ data :- alpha .
x :- x + y .
y :- x - y .
c :- c + 1 .
PRINT ( c ) .
Код: Выделить всё
VALID
Ввод:
Код: Выделить всё
PRINT ( a # b ) .
flag :- a > b .
a :- a - b . b :- b - a .
PRINT ( "Hello" & "World!" ) .
Код: Выделить всё
VALID
Ввод:
Код: Выделить всё
foo :- ( PRINT ) ;
PRINT ( * )
Код: Выделить всё
INVALID!
Error: factor expected, got "PRINT"
Пример 4
Ввод:
Код: Выделить всё
void getToken ( ) {
cin >> token ;
}
Код: Выделить всё
INVALID!
Error: ":-" expected, got "getToken"
Мой подход< /h1>
Учитывая грамматику, чтобы построить анализатор рекурсивного спуска сверху вниз, я следую следующей методике:
Для каждого нетерминала я разработал соответствующую функцию, которая анализирует предложения, которые могут быть сгенерированы этим нетерминалом.
Функция getToken() извлекает следующий токен из входных данных и сохраняет его в глобальном переменный токен.
Нетерминал, имеющий более одной продукции, требует проверки токена, чтобы определить, какую продукцию применить.
Токен сравнивается с первый символ в каждом произведении, пока не будет найдено совпадение.
Если совпадение не найдено, программа выдает ошибку и завершает работу.
Мой код
Код: Выделить всё
import sys
# Initialize token and jetton
token = None
jetton = 0
tokens = []
def getToken():
"""Fetches the next token from the input and increments jetton."""
global token, jetton
if tokens:
token = tokens.pop(0)
jetton += 2 # Increment jetton for each token
else:
token = None
def error(expected):
"""Raise an error with an expected message."""
print("INVALID!")
print(f"Error: {expected}, got '{token}'")
sys.exit(1)
def parse_Factor():
"""Parses the Factor rule."""
global token
if token.isdigit() or (token[0] in "+-" and token[1:].isdigit()): # Integer
getToken()
elif token.startswith('"') and token.endswith('"'): # String
getToken()
elif token.isidentifier(): # Identifier as a variable or designator
getToken()
elif token == "(":
getToken()
parse_Expression()
if token == ")":
getToken()
else:
error("')' expected")
elif token == "~":
getToken()
parse_Factor()
else:
error("Factor expected")
def parse_Term():
"""Parses the Term rule."""
parse_Factor()
while token in ["*", "/", "AND"]:
getToken()
parse_Factor()
def parse_SimpleExpression():
"""Parses the SimpleExpression rule."""
parse_Term()
while token in ["+", "-", "OR", "&"]:
getToken()
parse_Term()
def parse_Expression():
"""Parses the Expression rule."""
parse_SimpleExpression()
if token in ["", "=", "#"]: # Relation
getToken()
parse_SimpleExpression()
def parse_Designator():
"""Parses the Designator rule."""
if token.isidentifier():
getToken()
while token in ["^", "["]:
if token == "^":
getToken()
if token.isidentifier():
getToken()
else:
error("Identifier expected after '^'")
elif token == "[":
getToken()
parse_Expression()
if token == "]":
getToken()
else:
error("']' expected")
else:
error("Identifier expected")
def parse_Assignment():
"""Parses the Assignment rule."""
parse_Designator()
if token == ":-":
getToken()
parse_Expression()
if token == ".":
getToken()
else:
error("'.' expected")
else:
error("':-' expected")
def parse_PrintStatement():
"""Parses the PrintStatement rule."""
if token == "PRINT":
getToken()
if token == "(":
getToken()
parse_Expression()
if token == ")":
getToken()
if token == ".":
getToken()
else:
error("'.' expected")
else:
error("')' expected")
else:
error("'(' expected")
else:
error("'PRINT' expected")
def parse_Statement():
"""Parses a single Statement."""
if token.isidentifier():
parse_Assignment()
elif token == "PRINT":
parse_PrintStatement()
else:
error("Statement expected")
def parse_StatementSequence():
"""Parses the StatementSequence rule."""
while token:
parse_Statement()
def main():
"""Main function to handle input and parsing."""
global tokens
print("Enter your program (end input with Ctrl+D):")
try:
# Read program from standard input
program = sys.stdin.read()
# Tokenize by whitespace
tokens = program.split()
getToken() # Initialize first token
parse_StatementSequence() # Start parsing
print("VALID")
except Exception as e:
print(f"Error: {e}")
sys.exit(1)
if __name__ == "__main__":
main()
Для первых 3 входных образцов программа печатает «недействительный» с сообщением об ошибке, когда она должна печатать «Допустит».
Сообщения об ошибках:
Код: Выделить всё
(sample 1)
INVALID!
Error: ':-' expected, got '('
(sample 2)
INVALID!
Error: Factor expected, got 'i'
(sample 3)
INVALID!
Error: Factor expected, got 'i'
Подробнее здесь: https://stackoverflow.com/questions/792 ... ating-code
