Phân tích cú pháp

Phân tích một chuỗi ký hiệu, theo các quy tắc của một ngữ pháp hình thứcBản mẫu:SHORTDESC:Phân tích một chuỗi ký hiệu, theo các quy tắc của một ngữ pháp hình thức

Phân tích cú pháp (tiếng Anh: parsing, syntax analysis, hoặc syntactic analysis) là một quá trình phân tích một chuỗi các biểu tượng, sử dụng trong ngôn ngữ tự nhiên, ngôn ngữ máy tính và các cấu trúc dữ liệu, tuân theo các quy tắc của ngữ pháp hình thức (formal grammar). Thuật ngữ parsing đến từ từ Latin pars (orationis), nghĩa là từ loại.^[1]

Thuật ngữ này có đôi chút khác biệt trong các chuyên ngành ngôn ngữ học và khoa học máy tính. Phân tích cú pháp một câu truyền thống thông thường được thực thi dưới dạng một phương pháp hiểu ý nghĩa chính xác của một câu hoặc từ, đôi khi với sự trợ giúp của các thiết kế chẳng hạn như các biểu đồ câu. Theo đó, tầm quan trọng của các bộ phận ngữ pháp như chủ ngữ và vị ngữ được nhấn mạnh.

Thuật ngữ cũng được dùng trong ngôn ngữ học tâm lý khi mô tả sự hiểu biết ngôn ngữ. Trong bối cảnh đó, phân tích cú pháp là cách con người phân tích một câu hay cụm từ (trong tiếng nói hay văn bản) "xét theo các nhân tố cấu thành ngữ pháp, xác định các thành phần của lời nói, các quan hệ cú pháp,..."^[1] Thuật ngữ này đặc biệt phổ biến khi thảo luận về những tín hiệu ngôn ngữ nào giúp người nói diễn dịch câu đường đi trong vườn (garden-path sentence, câu lập lờ).

Với khoa học máy tính, thuật ngữ được dùng để phân tích ngôn ngữ máy tính, nhắc đến cách phân tích cú pháp của mã đầu vào thành các phần thành phần của nó nhằm tạo điều kiện thuận lợi cho việc viết trình biên dịch và trình thông dịch. Thuật ngữ cũng dùng cho việc mô tả sự tách biệt hay phân chia.

Ví dụ

Sử dụng thư viện spaCy để phân tích cú pháp của câu "Apple is looking at buying U.K. startup for $1 billion" bằng ngôn ngữ Python.

import spacy

nlp = spacy.load("en_core_web_sm")
doc = nlp("Apple is looking at buying U.K. startup for $1 billion")

for token in doc:
    print(token.text, token.lemma_, token.pos_, token.tag_, token.dep_,
            token.shape_, token.is_alpha, token.is_stop)

Xem thêm

Quay lui (khoa học máy tính)
Chart parser
Trình sinh bộ phân tích cú pháp
Deterministic parsing
String generation
Grammar checker
LALR parser
Phân tích từ vựng
Pratt parser
Shallow parsing
Left corner parser
Parsing expression grammar
ASF+SDF Meta Environment
DMS Software Reengineering Toolkit
Program transformation
Source code generation

Tham khảo

^ ^a ^b “Parse”. dictionary.reference.com. Truy cập ngày 27 tháng 11 năm 2010.

Đọc thêm

Chapman, Nigel P., LR Parsing: Theory and Practice, Nhà xuất bản Đại học Cambridge, 1987. ISBN 0-521-30413-X
Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0-13-651431-6

Liên kết ngoài

The Lemon LALR Parser Generator
Stanford Parser The Stanford Parser
Turin University Parser Natural language parser for the Italian, open source, developed in Common Lisp by Leonardo Lesmo, University of Torino, Italy.
Short history of parser construction

x t s Phân tích cú pháp
Top-down parsing	LL parser Recursive descent parser Tail recursive parser Pratt parser
Bottom-up parsing	Precedence Simple precedence parser Operator-precedence parser Shunting-yard algorithm Bounded-context LR parser Simple LR parser LALR parser Canonical LR parser GLR parser Thuật toán CYK Recursive ascent parser Shift-reduce parser
Hỗn hợp, khác	Parser combinator Chart parser Earley parser
Chủ đề liên quan	Parsing expression grammar Definite clause grammar Deterministic parsing Quy hoạch động Memoization Trình sinh bộ phân tích cú pháp LALR parser generator Cây phân tích cú pháp Cây cú pháp trừu tượng Scannerless parsing History of compiler construction Comparison of parser generators

x t s Chuỗi (khoa học máy tính)
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Khoảng cách Hamming Jaro–Winkler distance Lee distance Levenshtein automaton Khoảng cách Levenshtein Wagner–Fischer algorithm
Thuật toán tìm kiếm chuỗi	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Thuật toán Knuth–Morris–Pratt Rabin–Karp algorithm
Tìm kiếm nhiều chuỗi	Aho–Corasick algorithm Commentz-Walter algorithm
Biểu thức chính quy	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Bắt cặp trình tự	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Cấu trúc dữ liệu	Deterministic acyclic finite state automaton Suffix array Suffix automaton Cây hậu tố Generalized suffix tree Rope (data structure) Ternary search tree Trie
Khác	Phân tích cú pháp Pattern matching Compressed pattern matching Longest common subsequence problem Bài toán xâu con chung dài nhất Sequential pattern mining Category:String sorting algorithms