ไวยากรณ์หลัก

Q: รูปแบบของกฎเกณฑ์

กฎไวยากรณ์หลักถูกกำหนดโดยใช้การดำเนินการสองอย่างนี้ โดยกฎจะมีรูปแบบใดรูปแบบหนึ่งดังต่อไปนี้

ไวยากรณ์หัว ( HG ) เป็นรูปแบบไวยากรณ์ที่นำเสนอโดยCarl Pollard (1984) ^{[ 1 ]}เป็นส่วนขยายของ ไวยากรณ์ แบบไร้บริบท ไวยากรณ์ หัวจึงเป็น ไวยากรณ์โครงสร้างวลีประเภทหนึ่งตรงข้ามกับไวยากรณ์การพึ่งพา ไวยากรณ์หัวเป็นกลุ่มย่อยของ ระบบการเขียน ใหม่แบบไร้บริบทเชิงเส้น

วิธีทั่วไปวิธีหนึ่งในการกำหนดไวยากรณ์หัว (head grammars) คือการแทนที่สตริงเทอร์มินัลของไวยากรณ์แบบบริบทอิสระ (CFG) ด้วยสตริงเทอร์มินัลที่มีดัชนี โดยที่ดัชนีจะระบุคำ "หัว" ของสตริงนั้น ตัวอย่างเช่น กฎ CF เช่น $A\to abc$ อาจจะเป็นแทน $A\to (abc,0)$ โดยที่เทอร์มินัลที่ 0 คือaซึ่งเป็นหัวของสตริงเทอร์มินัลที่ได้ เพื่อความสะดวกในการเขียน อาจเขียนกฎดังกล่าวเป็นเพียงสตริงเทอร์มินัล โดยใช้เครื่องหมายบางอย่างแทนเทอร์มินัลหัว ดังเช่นใน $A\to {\widehat {a}}bc$ .

จากนั้นจึงมีการเพิ่มการดำเนินการพื้นฐานสองอย่างเข้าไปในกฎการเขียนใหม่ทั้งหมด ได้แก่ การห่อและการต่อข้อความ

การดำเนินการกับสตริงที่มีหัว

การห่อ

การห่อสตริงเป็นการดำเนินการกับสตริงที่มีสองส่วนหัว ซึ่งกำหนดไว้ดังนี้:

อนุญาต $\alpha {\widehat {x}}\beta$ และ $\gamma {\widehat {y}}\delta$ เป็นสตริงปลายทางที่ขึ้นต้นด้วยxและyตามลำดับ

$w(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\gamma {\widehat {y}}\delta \beta$

การต่อกัน

การต่อสตริงเป็นกลุ่มของการดำเนินการกับสตริงที่มีหัว n > 0 โดยกำหนดไว้สำหรับ n = 1, 2, 3 ดังนี้:

อนุญาต $\alpha {\widehat {x}}\beta$ , $\gamma {\widehat {y}}\delta$ , และ $\zeta {\widehat {z}}\eta$ เป็นสตริงปลายทางที่ขึ้นต้นด้วยx , yและzตามลำดับ

$c_{1,0}(\alpha {\widehat {x}}\beta )=\alpha {\widehat {x}}\beta$

$c_{2,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha {\widehat {x}}\beta \gamma y\delta$

$c_{2,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\beta \gamma {\widehat {y}}\delta$

$c_{3,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha {\widehat {x}}\beta \gamma y\delta \zeta z\eta$

$c_{3,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha x\beta \gamma {\widehat {y}}\delta \zeta z\eta$

$c_{3,2}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha x\beta \gamma y\delta \zeta {\widehat {z}}\eta$

และอื่นๆ ต่อไปอีก $c_{m,n}:0\leq n<m$ เราสามารถสรุปรูปแบบนี้ได้ง่ายๆ ว่า "นำสตริงปลายทางm จำนวนหนึ่งมาต่อ กัน โดยกำหนดให้หัวของสตริงnเป็นหัวของสตริงที่ได้"